经验总结

  1. 首页 > 生活 > >

我说HashMap初始容量是16，面试官让我回去等通知

生活百科

众所周知HashMap是工作和面试中最常遇到的数据类型，但很多人对HashMap的知识止步于会用的程度，对它的底层实现原理一知半解，了解过很多HashMap的知识点，却都是散乱不成体系，今天一灯带你一块深入浅出的剖析HashMap底层实现原理 。
看下面这些面试题，你能完整的答对几道？
1. HashMap底层数据结构？JDK1.7采用的是数组+链表，数组可以通过下标访问，实现快速查询，链表用来解决哈希冲突 。
链表的查询时间复杂度是O(n)，性能较差，所以JDK1.8做了优化，引入了红黑树，查询时间复杂度是O(logn) 。
【我说HashMap初始容量是16，面试官让我回去等通知】JDK1.8采用的是数组+链表+红黑树的结构，当链表长度大于等于8，并且数组长度大于等于64时，链表才需要转换成成红黑树 。

我说HashMap初始容量是16，面试官让我回去等通知

文章插图
2. HashMap的初始容量是多少？如果面试的时候，你回答是16，面试官肯定让你回去等通知 。
JDK1.7的时候初始容量确实是16，但是JDK1.8的时候初始化HashMap的时候并没有指定容量大小，而是在第一次执行put数据，才初始化容量 。
// 负载因子大小final float loadFactor;// 默认负载因子大小static final float DEFAULT_LOAD_FACTOR = 0.75f;// 初始化方法public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;}执行new HashMap()方法初始化的时候，只指定了负载因子的大小 。
3. HashMap的put方法流程？
  1. 计算key的哈希值
  2. 判断数组是否为空，如果为空，就执行扩容，初始化数据大小 。
  3. 如果数组不为空，根据哈希值找到数组所在下标
  4. 判断下标元素是否为null，如果为null就创建新元素
  5. 如果下标元素不为null，就判断是否是红黑树类型，如果是，则执行红黑树的新增逻辑
  6. 如果不是红黑树，说明是链表，就追加到链表末尾
  7. 如果判断链表长度是否大于等于8，数组长度是否大于等于64，如果不是就执行扩容逻辑
  8. 如果是，则需要把链表转换成红黑树
  9. 最后判断新增元素后，判断元素个数是否大于阈值（16*0.75=12），如果是则执行扩容逻辑，结束 。

我说HashMap初始容量是16，面试官让我回去等通知

文章插图
源码如下：
// put方法入口public V put(K key, V value) {// 计算哈希值return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 判断数组是否为空，为空的话，则进行扩容初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 计算数组下标位置，判断下标位置元素是否为nullif ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 数组中已经存在元素（处理哈希冲突）else {Node<K,V> e; K k;// 判断元素值是否一样，如果一样则替换旧值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 判断元素类型是否是红黑树else if (p instanceof TreeNode)// 执行红黑树新增逻辑e = ((TreeNode<K,V>)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 )，执行 treeifyBin 方法// 这个方法会根据 HashMap 数组来决定是否转换为红黑树 。// 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间 。否则，就是只是对数组扩容 。if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// 判断链表中结点的key值与插入的元素的key值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循环break;// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表p = e;}}// 表示在数组中找到key值、哈希值与插入元素相等的结点if (e != null) {// 记录e的valueV oldValue = https://www.huyubaike.com/biancheng/e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue == null)//用新值替换旧值e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 记录修改次数++modCount;// 元素个数大于阈值则扩容if (++size > threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;}

经验总结扩展阅读


上一篇：三伏天羊肉炖什么最好

下一篇：三伏天的搞笑谚语