常规集合中用的最多的是ArrayList，LinkedList，HashMap，内部数据结构分别是：数组，列表，以及数组，列表，二叉树(红黑树)。分别实现：不排序(是否按照大小排序)有序(插入顺序)集合，排序无序集合， key/value存储。这三个也是面试中经常能遇到的，我就遇到过很多次，虽说能理解内部结构但对实现细节了解不到位，回答的可想而知。本文就一次插到低，从此对面试官说去你MA的。
下面我们从自己去实现这三个集合的角度去思考。如果如果实现就需要考虑如下问题：
基础知识底层数据结构
存储不够怎么扩展
数据量少了要不要缩减空间
各种 *** 作复杂程度
是否进行排序
是否添加顺序有序
并发支持，怎么支持
并发 *** 作不同怎办
怎么存储不同类型不同形态的数据
数据结构.红黑树 Red Black Tree 自平衡二叉树
Java.集合 框架，接口，常用集合特点比对
Java多线程.系列内容目录
术语排序： 是否按照元素大小排序，插入数据后，这个列表是否完成了排序，按照自己提供的迭代器可以输出就算
有序：插入数据的先后顺序，怎么存储不管，是否可以通过某种方法，可以遍历出来就算
列表：一些数字或者对象 的集合
链表：数据结构中的类似锁链的一种集合数据存储结构
英文能力ensure 确保
capacity 容量
Internal 内部
explicit 明确的
overflow 溢出
Sequential 顺序式
Linked 链接，关联( 不是有序的意思）
factor 因素 因子
ArrayList 用什么样的数据结构存储集合呢-- 数组/链表，数组大小固定，链表到是可以无限链接下去，这里用数组吧，后面再实现一个链表的
数组是固定长度的，是否要初始化，初始化多少呢？-- (1.7前) 初始化10个元素，10怎么来的，总得初始化一个大小吧
-- (1.8后) 懒加载，第一次Add的时候初始化为10个
怎么存储不同类型不同形态的数据-- 实现方法，Object[] 泛型
-- 存储空间：Object[] elementData
-- *** 作：public boolean add(E e)
无论初始化多少，也有不够用的时候，按照啥规则扩展容量？-- 添加一个或者多个元素，扩展至少保证最需要需求，除非超过Integer.MAX_VALUE(JVM限制的，部分VM会预留部分表头，所以一般别超过Integer.MAX_VALUE-8个元素)
-- 扩容规则还是看代码吧
// minCapacity 最小的容量，取值：oldCapacity + 本次增量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 增量为： 旧容量的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果增量超过，旧容量的一半。就取 增量长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果超过Integer.MAX_VALUE - 8，则取Integer.MAX_VALUE
// 为什么预留8个位置，是部分VM会预留部分表头空间
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}-- 添加：元素从前往后放，size指向下一个位置的下标；可重复，可为null，列表中的下标顺序就是添加的顺序
-- 删除：中间删除元素，后边的元素挨个移动到前面，也会保持顺序
数据量少了要不要缩减空间-- remove方法中没有看到有空间缩小的逻辑
并发支持，怎么支持-- 多个线程 *** 作就 *** 作呗，不支持的是：遍历和 其他 *** 作 并行，会触发ConcurrentModificationException异常，这就是所谓的：fast-faild
ArrayList list = new ArrayList<>();
list.add("11");
// 记录modCount
Iterator iterator1 = list.iterator();
// modCount ++
list.remove("11");
// 检查 modCount 是不是我new iterator的时候记录的
iterator1.next();
// 并不更新modCount
iterator1.remove();
// 当然就没哟异常了
iterator1.next(); -- 线程不安全，咱就不要探究哪个方法支持，哪个方法不支持，咱们就应该避免这样的事发生。 比如：add 重新分配空间，导致空间变动，如果其他线程换在iterator遍历，遍历的是旧的。
-- 如果需要线程安全，三种方法：
1. 外边加锁，保持ArrayList的单线程 *** 作；
2. ArrayList方法上synchronized，SynchronizedList list = Collections.synchronizedList(new ArrayList()), 避免不了fast-faild问题。监控的是list对象
3. synchronized太重，用ReentrantLock，类：CopyOnWriteArrayList，该类iterator不检查版本
总结：从上面总结出来的是否进行排序： 无序状态
是否添加顺序有序 ： 数组从前到后
并发支持，怎么支持 ： 要完全避免线程安全问题，并让结果可预期，就不要并发 *** 作
并发 *** 作不同怎办： 遍历和删除会触发fast-faild机制；其他
各种 *** 作复杂程度
ListIterator1. 添加不扩容：O(1)
2. 检索：O(n)
3. 扩容：O(n)
4. 删除：检索O(n) + 复制元素O(n)
更强大的遍历迭代器，可以双向移动。只是遍历双向的，因为底层还是数组，没法像连表一样扩展，所以用来做队列不是好的选择。
但如果要自己用两个下标start，end 来玩队列，也不是不可以，太复杂了。
LinkedList 底层数据结构-- 看名称是想做一个排序的列表，既然是排序用链表好一点，并且是双向链表(没有表头)
存储不够怎么扩展 -- 不存在这个问题
数据量少了要不要缩减空间-- 不存在这个问题
各种 *** 作复杂程度-- 都是检索的复杂度O(n)，找到就直接 *** 作完事，双直针也省了
是否进行排序-- 明知道顾问，不排序
LinkedList list = new LinkedList();
list.add(1);
list.add(3);
list.add(2);
// 1 3 2
for(Integer i : list){
System.out.print(i + " ");
}
-- add 的顺序就是 foreach的顺序，有序
并发支持，怎么支持-- 不支持，要不自己加锁synchronized，要不 Collections.synchronizedList 包起来
并发 *** 作不同怎办
-- 也有fast-faild机制
怎么存储不同类型不同形态的数据-- 泛型Node
数组添加元素，扩容太费劲，删除需要移动数组。双向列表呢，搜索 *** 作位置的时间是必须的。
需求：能不能有一种结构，能实现O(1)的，梦想可以有的，怎么实现呢
底层数据结构思路：按照地址访问是O(1)， 如果node可以跟 地址有个映射就可以了。 链表的节点地址完全不确定，排除；数组地址倒是固定，能用到地址也就是一个偏移量，总不能跟0x****这样的地址对应吧，out：node跟地址偏移量[0,n] 映射，这个映射算法在hashCode实现
如果一个node经过hash后可以唯一对于一个[0,n] 就很OK，但必然会有重复的情况。如果两个node的hash值都是1咋搞？
如果这个节点有值了，并且薪添加的node也落入这个节点，那就挂起来。结构有两种如下图，区别：数组是否存储数据，第二个能省空间。
问题又来了，怎么平衡数组长度和总数量量呢，数组短，都成了直接访问链表。数组长？ 那啥时候应该给数组扩容，扩多少呢？
存储不够怎么扩展什么时候扩：size > (capacity * load factor) (size 现有数据量，capacity 容量-数组的长度，load factor 加载因子默认0.75)
capacity 容量-数组的长度 - 会取2的次幂，跟后边的Hash算法相关，将方法：tableSizeFor
扩多少，怎么扩：见resize代码。不考虑边界，capacity 扩展2倍，即数组长度。复制节点：
1. 如果普通数据节点，则直接赋值到新数组中即可
2. 如果是链表或者红黑树节点，则按照 hash<=oldCap为边界 拆分两个节点结合，然后根据数量重新组织，拆分后的节点少于6 UNTREEIFY_THRESHOLD就组织为链表，超过则组织为树结构
final java.util.HashMap.Node[] resize() {
// 记录数组
java.util.HashMap.Node[] oldTab = table;
// 记录原始数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 记录原始阈值(跟数组长度比对)
int oldThr = threshold;
int newCap, newThr = 0;
// 如果数组已经初始化
if (oldCap > 0) {
// 如果旧的数组容量已经>= 1的30次方
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值取Integer类型的最大值
threshold = Integer.MAX_VALUE;
// 数组不变
return oldTab;
}
// 如果没超过，容量扩容一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果原容量已经超过16，阈值也翻倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 数组还没有初始化
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 否则按照默认16初始化容量，阈值按照容量16*加载因子0.75来算=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 搂个底，并控制最大容量边界条件，设置新的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 设置阈值，新建数组，并给table赋值新数组引用
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
java.util.HashMap.Node[] newTab
= (java.util.HashMap.Node[])new java.util.HashMap.Node[newCap];
table = newTab;
// 处理旧数组
if (oldTab != null) {
// 遍历数组
for (int j = 0; j < oldCap; ++j) {
java.util.HashMap.Node e;
// 如果该数组元素有数据，并赋给中间变量e
if ((e = oldTab[j]) != null) {
// 清空数组元素
oldTab[j] = null;
// 如果该bulket只有一个数据,给新数组赋值
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof java.util.HashMap.TreeNode)
// 如果是红黑树 则将hash值<=oldCap为边界 拆分为两个列表，即：hash值大小
((java.util.HashMap.TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
java.util.HashMap.Node loHead = null, loTail = null;
java.util.HashMap.Node hiHead = null, hiTail = null;
java.util.HashMap.Node next;
do {
next = e.next;
// 如果是普通链表，则将hash值<=oldCap为边界 拆分为两个列表，即：hash值大小
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 从中体验下结构：
1. 数组槽位下标计算：(数组长度 - 1) & hash(key)
2. 怎么判断两个节点是一个Node： hash值一样，key是==，如果不是null 则equals方法
3. 链表元素超过8 TREEIFY_THRESHOLD个，就转为树
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
java.util.HashMap.Node[] tab; java.util.HashMap.Node p; int n, i;
// 如果数组还空着，则初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 数组i 还没有存储数据，就new java.util.HashMap.Node存储数据即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 该槽位已有数据，p是该数组元素
java.util.HashMap.Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果数组原始 和 新数的hash值一样，找到目标元素了，就是当前数组元素节点，后面会根据e赋值value呢
e = p;
else if (p instanceof java.util.HashMap.TreeNode)
// 如果是树节点
e = ((java.util.HashMap.TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 找链表尾结点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果超过8，将列表转为红黑树，跳出来
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果hash值相同，并且key值一样，那么就返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 赋值value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 雷同新增节点中的查重逻辑
不同是：加入树删除的少于UNTREEIFY_THRESHOLD了，不会转为链表。 树转链表，只有resize 方法内用到。
并发支持hashMap就是简单的数组和链表，并没有控制并发的锁机制，所以是线程不安全的。如果并发 *** 作：可能的动作是数组，链表，树并发 *** 作的结果，天知道。
如果需要：
1. 外部代码控制锁
2. 或者使用HashTable，或者ConcurrentHashMap
其他特征数据量少了要不要缩减空间： 看情况
各种 *** 作复杂程度： 看情况
是否进行排序：无序
是否添加顺序有序：无序
怎么存储不同类型不同形态的数据：泛型
什么用红黑树，不用二叉树，平衡二叉树之所以不用二叉树：
红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。
之所以不用平衡二叉树：
平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。
红黑树怎么保持平衡的知道吗？
红黑树有两种方式保持平衡：旋转和染色。
旋转：旋转分为两种，左旋和右旋
Hash函数怎么设计的，怎么保证每个槽位数量的离散性 hashHashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或 *** 作。
后边在hashCode基础上高低16位异或 ，有人称之为“扰动函数”，目的当然是为了更好的让hash值能均匀分布，为什么？ -- 不清楚
static final int hash(Object key) {
int h;
// key的hashCode和key的hashCode右移16位做异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647，加起来大概 40 亿的映射空间。
只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。
假如 HashMap 数组的初始大小才 16，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。
源码中模运算就是把散列值和数组长度 - 1 做一个 “与&” *** 作，位运算比取余 % 运算要快。
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length-1);
}
这样是要快捷一些，但是新的问题来了，就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。
这时候 扰动函数的价值就体现出来了，看一下扰动函数的示意图：
右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
为什么HashMap的容量是2的倍数呢？源码解读参考第一个原因是为了方便哈希取余：
将元素放在table数组上面，是用hash值%数组大小定位位置，而HashMap是用hash值&(数组大小-1)，却能和前面达到一样的效果，这就得益于HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一位为1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和%一样的效果，并且位运算比%的效率高得多
HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。
第二个方面是在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去.
HashMap源码解读—Java8版本_步尔斯特的博客-CSDN博客
LinkedList源码解读—Java8版本_步尔斯特的博客-CSDN博客
ArrayList源码解读—Java8版本_步尔斯特的博客-CSDN博客
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）