Java.ArrayList LinkedList HashMap JDK8版本
常规集合中用的最多的是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 = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
Add元素怎么放,删除的时候怎么删除
-- 添加:元素从前往后放,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机制;其他
各种操作复杂程度
1. 添加不扩容:O(1)
2. 检索:O(n)
3. 扩容:O(n)
4. 删除:检索O(n) + 复制元素O(n)
ListIterator
更强大的遍历迭代器,可以双向移动。只是遍历双向的,因为底层还是数组,没法像连表一样扩展,所以用来做队列不是好的选择。
但如果要自己用两个下标start,end 来玩队列,也不是不可以,太复杂了。
LinkedList
底层数据结构
-- 看名称是想做一个排序的列表,既然是排序用链表好一点,并且是双向链表(没有表头)
存储不够怎么扩展 -- 不存在这个问题
数据量少了要不要缩减空间-- 不存在这个问题
各种操作复杂程度
-- 都是检索的复杂度O(n),找到就直接操作完事,双直针也省了
是否进行排序
-- 明知道顾问,不排序
LinkedList list = new LinkedList();list.add(1);list.add(3);list.add(2);// 1 3 2for(Integer i : list){System.out.print(i + " ");}
是否添加顺序有序
-- add 的顺序就是 foreach的顺序,有序
并发支持,怎么支持
-- 不支持,要不自己加锁synchronized,要不 Collections.synchronizedList 包起来
并发操作不同怎办
-- 也有fast-faild机制
怎么存储不同类型不同形态的数据
-- 泛型Node存储数据
HashMap
为什么要有HashMap
数组添加元素,扩容太费劲,删除需要移动数组。双向列表呢,搜索操作位置的时间是必须的。
需求:能不能有一种结构,能实现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) = DEFAULT_INITIAL_CAPACITY) // 如果原容量已经超过16,阈值也翻倍 newThr = 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 1sttreeifyBin(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函数怎么设计的,怎么保证每个槽位数量的离散性
hash
HashMap的哈希函数是先拿到 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);}
为什么哈希/扰动函数能降hash碰撞
因为 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博客
创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖