面试官：小伙子，了解HashMap吗?
学弟：哎呦，你干嘛～ 真的问这个呀…
面试官：练习时长两年半？待会答不上来，你可就遭老罪喽！

那行吧，那开始吧…唱跳rap篮球🏀…

一、HashMap的底层结构

说一下你理解的HashMap底层？

hashMap是由数值和链表组合而成的数据结构，存储为key Value形式。

在java7中叫entry，数据形式为数组+链表。java8中叫Node，数据形式为数组+链表+红黑树（当链表长度大于8时转为红黑树）。

每一个节点都会保存自身的hash、key、value、以及next属性指向下一个节点。

二、为什么使用数组+链表数据结构

你刚提到了使用数组+链表，可以讲讲为什么使用这个结构吗？

HashMap内部使用数组来存储键值对，这个数组就是 HashMap 的主体。

在数组中存储的每个位置上，可能会有多个键值对，这些键值对通过链表的形式链接在一起。

使用数组+链表的数据结构是为了解决散列表中的键冲突问题。在散列表中，每个键都会被映射到一个桶中，但是不同的键可能会被映射到同一个桶中，这种情况被称为键冲突。

为了解决键冲突问题，HashMap 采用了链表的形式将所有映射到同一个桶中的键值对链接在一起，这样就可以通过遍历链表来查找指定键的值。当链表长度过长时，查找效率就会下降，因此在链表长度超过一定阈值（8）后，HashMap会将链表转换为红黑树，以提高查找效率。

同时，数组的优势在于支持通过下标快速访问元素，因此HashMap可以将每个桶的位置映射到数组的一个元素上，通过下标访问该元素即可访问到对应的链表或红黑树。

我们都知道：数组的查询效率很高，添加和删除的效率低。链表的查询效率很低，添加和删除的效率高。

因此：使用数组加链表形式，不仅可以解决散列表中的键冲突问题，且数组的查询效率高、链表的添加和删除效率高。结合在一起，增删查效率都很高。

嗯，确实不错。不愧是练习时长两年半的程序员…

三、数组+链表+红黑树

你刚说数组+链表+红黑树，什么情况下会转化红黑树？什么情况下转数组呢？

链表中元素过多，会影响查找效率，当其个数达到8的时候转换为红黑树。红黑树是平衡二叉树，在查找性能方面比链表要高。

当红黑树的节点数小于等于6时，红黑树转换为链表，是为了减少内存开销。

需要注意的是：将链表转换为红黑树、红黑树转换为链表的操作会影响HashMap的性能，因此需要尽可能避免这种情况的发生。同时，当HashMap中的元素数量较小时，不会出现链表转换为红黑树的情况，因此使用HashMap时，可以考虑在元素数量较少的情况下使用HashMap，以提高性能。

四、头插法和尾插法

说一下什么是头插法，什么是尾插法？

哇，这不是为难我胖虎吗？啥是头插法？啥是尾插法？

4.1、头插法

顾名思义，头插法就是新增元素时，放在最前面嘛。

举个栗子🌰，楼主画了一个简单的框框。用来表示原有存储顺序依次为1、2、3的数组。

假设现在加入了一个4，如果使用头插法，就会变为4123。

4.2、尾插法

同样道理，尾插法就是新增元素时，放在最后面。

还是原有存储顺序依次为1、2、3的数组。

假设现在加入了一个4，如果使用尾插法，就会变为1234。

头插法为什么要调整为尾插法呢？

为什么头插法要调整为尾插法？这是个好问题！！！

java7中使用头插法，新来的值会取代原有的值，原有的值就顺推到链表中。在这种情况下，引用关系可能会乱掉，严重会造成死循环。java8使用尾插法，把元素放到最后，就不会出现这种情况。

五、HashMap如何运算存储索引

向一个hashMap中存入数据时，如何知道数据放在哪个位置呢？

当向一个hashMap中存入数据时，会先根据key的哈希值决定放在数组中哪个索引位置。

Hash公式：index = HashCode（Key） & （Length - 1）

如果数组中该索引位置是空的，直接将元素放入，如果该索引位置已经存在元素了，就根据equals方法判断下已有的元素是否和我们新放入的元素是同一个，如果返回true是同一个，则覆盖掉。不是同一元素则在原有元素下面使用链表进行存储。

每个元素都有一个next属性指向下一个节点（数组+链表）

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        .........
    }

六、HashMap初始化、扩容

嗯，你知道HashMap默认初始化大小是多少吗？还有它的扩容？

HashMap默认初始化容量大小是16，最大容量为2的30次方，负载因子是0.75。

扩容时，会把原有数组中的值取出再次hash到新的数组中（长度扩大以后，Hash的规则也随之改变），因此性能消耗也相对较大。

当HashMap中的元素数量超过负载因子（默认为 0.75）乘以数组长度时，就会触发扩容操作，将数组长度增加一倍，并重新计算每个元素在新数组中的位置。

七、hash碰撞是什么

你听说过hash碰撞吗？

hash碰撞就是不同的Key，经过同一散列算法之后得到的hashCode值相同。

hashCode不同，key一定不同。hashCode相同，key却不一定相同。

当两个key的hashCode()返回值不同时，它们对应哈希表索引也一定不同。不同的key对象，即使它们包含相同的属性、值或状态，它们的hashCode()返回值也是不相同的。

当两个key的hashCode()返回值相同时，它们可能对应同一个哈希表索引，但它们并不一定相等。在哈希表中，不同的key可能会产生相同的哈希值（哈希碰撞）。

因此，当 key的hashCode相同时，还需要比较key的相等性。需要调用key的equals() 方法来判断它们是否相等。只有当hashCode相等，且equals方法返回true时。才可以认为这两个key相等。

八、如何解决hash碰撞

解决hash碰撞的方法有哪些呢？

在哈希表中，哈希碰撞可能会导致性能下降或者安全问题。

常见的解决方法有：

1、开放地址法：在发生哈希碰撞时，通过一定的算法在哈希表中寻找一个空闲的位置，并将元素插入该位置。

2、链式哈希表：在每个哈希表的元素位置上，存储一个链表，哈希碰撞时，将元素插入到相应的链表中。

3、再哈希法：如果一个哈希函数产生的哈希值发生了碰撞，就再次使用另一个哈希函数计算哈希值。

4、负载因子调整：通过调整哈希表的容量、负载因子等参数，可以减少哈希碰撞的发生。

九、HashMap为什么线程不安全

HashMap线程安全吗？为什么？

HashMap是非线程安全的。在多线程环境下，如果多个线程同时修改HashMap中的数据，就可能会导致数据的不一致性。

说白了就是没加锁。

当多个线程同时调用HashMap的put()方法，一旦他们计算出的hash值相同，就会发生冲突，导致数据被覆盖。

所以，对于多线程并发访问的情况，建议使用线程安全的Map实现。

例如ConcurrentHashMap，或者使用Collections.synchronizedMap()方法将HashMap包装成一个线程安全的Map。

十、HashMap、HashTable、ConcurrentHashMap的区别

最后一个问题：说一下HashMap、HashTable、ConcurrentHashMap的区别？

麻了! 真的麻了…救救孩子吧…

HashMap、HashTable、ConcurrentHashMap都是Java中常用的哈希表实现。

区别主要在以下几个方面：

1、线程安全性：HashTable是线程安全的，HashMap是非线程安全的，ConcurrentHashMap通过分段锁的方式保证了线程安全。

2、是否可为空：HashTable不允许null值作为key或value，而HashMap和ConcurrentHashMap则允许null作为key或value。

3、迭代器：HashTable的迭代器是通过Enumeration实现的，而HashMap和ConcurrentHashMap使用的是Iterator实现的。

4、扩容：HashTable在扩容时，将容量扩大一倍加一，而HashMap和ConcurrentHashMap的扩容机制是将容量扩大一倍。

5、初始容量：HashTable的初始容量为11，而HashMap和ConcurrentHashMap的初始容量为16。

6、性能：HashMap通常比HashTable性能更好，因为它没加锁。所以弊端就是线程不安全。但后者加了锁，是线程安全的，缺点就是消耗性能。ConcurrentHashMap在多线程并发访问时，比HashTable和HashMap性能更好，因为它使用了分段锁来保证线程安全。

所以，不建议使用HashTable。至于选择HashMap还是ConcurrentHashMap取决于并发访问量的大小，若并发访问量不高，则选用HashMap。若并发访问量较大，则选用ConcurrentHashMap。

ok，那今天先到这里吧。练习时长两年半的程序员…唱跳rap篮球🏀…差点就遭老罪喽～

还有，别忘记给那个练习时长两年半的三婶儿也点个赞哈～她唱跳rap篮球也还行…