集合面试题笔记
6319 HashMap 原理 数据结构：数组 + 链表 （JAVA8之后：数组+链表+红黑树） 数据结构 jdk1.7：数组+链表，数组每个元素是一个链表的表头，当发生冲突，将新元素添加在头部(头插法) hash冲突：头插法，❗扩容时可能造成环形链表 jdk1.8： 引入红黑树，当链表节点超过8个，那么这个链表会转换为红黑树。查询时间由 O(n) 优化为 O(logn)。当节点小于6个，再转换为链表。 hash冲突：尾插法，避免环形链表❗ 扩容机制 jdk1.7 扩容，元素会重新计算hash值，并分配到新的扩容数组中。⭐比较耗时 扩容时，头插法，在多线程情况下，可能造成环形链表 jdk1.8 扩容时，利用了元素哈希值和旧数组容量关系，减少了重新计算的哈希次数 扩容时，尾插法，避免环形链表 使用键的hashcode()计算hash值，然后(n-1) & hash确定数组中的位置。 n-1 => 10000 - 1 = 01111 HashMap的初始默认容量为16，负载因子为0.75。当存储的元素达到75%时，进行扩容，扩容为原来的2倍空间 扩展知识： hashmap的红黑树优化： JAVA8开始，为了优化hash冲突时的查找性能。但链表的长度超过8时，链表会转变为红黑树。红黑树是一种自平衡的二叉搜索树 查找时间 O(n) => O(logn)。 当元素少于6个，切换为链表 hashCode() 和 equals()的重要性： hashCode计算hash值，决定键的存储位置。 而hashCode相同=>冲突。 equals()比较的值 1// HashMap Node class 2static class Entry<K,V> { 3 final K key; // 键 4 V value; // 值 5 final int hash; // 计算后的哈希值 6 Entry<K,V> next; // 指向下一个元素的指针（形成链表） 7} 为什么头插法&多线程&扩容会造成环形链表? ...