主要考虑 3 个问题
主要的操作
扩容的策略
数据迁移策略
其中, 主要操作如下:
PS. 注意没有插入操作, 只有添加, 删除, 查找, 修改操作.
- type ArrayInterface interface {
- // 添加
- Add(int, interface{}) // 插入元素
- AddLast(interface{})
- AddFirst(interface{})
- // 删除
- Remove(int) interface{}
- RemoveFirst() interface{}
- RemoveLast() interface{}
- // 查找
- Find(interface{}) int // 查找元素返回第一个索引
- FindAll(interface{}) []int // 查找元素返回所有索引
- Contains(interface{}) bool // 查找是否存在元素
- Get(int) interface{}
- // 修改
- Set(int, interface{})
- // 基本方法
- GetCapacity() int // 获得数组容量
- GetSize() int // 获得元素个数
- IsEmpty() bool // 查看数组是否为空
- }
大概有 3 种设计方案
普通方案: 两倍扩容 + 挨个元素拷贝.
仿造 slice 切片的方案: 数组做底层存储 + 类似窗户的索引 + 更灵活的扩容 + 数组整体拷贝.
删除元素时不需要真的删除, 只是移动索引.
增加元素时需要往底层数组添加元素, 且移动索引.
加入 COW 机制的方案: 针对多线程读多写少场景.// 附录 2
方案 1
// 附录 1
方案 2: slice 的方案
扩容策略: 比较复杂
数据迁移策略: 整体拷贝
方案 3: 针对并发读多写少的优化
CopyOnWriteArrayList 使用场景
1, 读多写少 (白名单, 黑名单, 系统配置的信息, 商品类目的访问和更新场景), 为什么? 因为写的时候会复制新集合.
2, 集合不大, 为什么? 因为写的时候会复制新集合.
实时性要求不高, 为什么, 因为有可能会读取到旧的集合数据.---- 也就是允许读到旧数据.
方案 4
// 附录 4
Q:golang 的 slice 动态扩展实现为何不用动态链表?
A: 对内存不优化, 有 gc 压力.
扩展
slice 并发不安全的问题 https://www.cnblogs.com/yudidi/p/12614447.html
参考
Go 语言实现动态数组 https://segmentfault.com/a/1190000015680429#item-4
简单说一说 Java 中的 CopyOnWriteArrayList https://juejin.im/post/5aaa2ba8f265da239530b69e
并发容器之 CopyOnWriteArrayList https://juejin.im/post/5aeeb55f5188256715478c21
golang 的 slice 动态扩展实现为何不用动态链表? https://www.zhihu.com/question/47527916
来源: http://www.bubuko.com/infodetail-3487415.html