Java中的HashMap的原理

说白了 HashMap 底层就是一个数组，然后组合了链表和红黑树

怎么寻址

当你存一个 Key-Value 的时候会计算出 key 的 hashcode，然后用哈希计算公式
keyhashcode % (table.length - 1) 算出需要存放的位置

处理哈希冲突

按照上面说的寻址我们会发现，有概率两个元素用公式算出来的结果是一样的，这就是我们常说的哈希冲突，HashMap 里也设定好了解决方法：

• 链表：Java 7 及以前是把他们放在一起，用链表装着
  • 在 java 7 及以前链表使用的是头插法，即每次出现哈希冲突时，新的节点会插入到链表的头节点，老节点以此往后，在多线程环境下，头插法可能导致链表形成环，特别是在并发扩容时 rehashing 。当多个线程同时执行 put() 操作时，如果线程 A 正在进行头插，线程 B 也在同一时刻操作链表，可能导致链表结构出现环路，从而引发死循环，最终导致程序卡死或无限循环。
  • 但在 java 8 的时候改为尾插法，即新的节点插入到链表的尾部，保持链表的流畅度
• 红黑树：
  • Java 8 后做了优化，如果同一个下标的元素太多了（超过八个），则将链表转换成红黑树
  • 红黑树是一个自动平衡二叉树，能够将最坏情况下的查找复杂度从O(n) 变成 O(logn)
  • 如果数中的数量低于6，红黑树将会转换回链表，以减少不必要的开销

扩容机制

HashMap 默认长度是16，HashMap 有扩容因子（默认是0.75），意思是当元素超过 长度 * 0.75 时将会自动扩容。

默认长度是 16，扩容因子是 0.75，这个组合是性能和空间之间找到的平衡。如果扩容因子过高，虽然空间利用更高了，但是更容易出现哈希冲突，影响效率；如果扩容因子过低，哈希冲突出现概率减少，但是空间利用率低。

扩容就算将容量翻倍，然后把位置重新计算一遍，放进新的数组。

HashCode() 和 equals() 的重要性

HashMap 的 key 必须实现 HashCode() 和 equals() 方法。

• hashcode() 用于计算哈希值，以决定键的存储位置
• 而 equals() 用于比较两个键是否相同。

在 put 操作的时候需要用到这两个方法来计算存放的位置，误用 HashCode() 和 equals() 可能导致存放错误

注意：这个操作挺耗费性能的，所以我们尽量在初始化的时候就给个大概容量，少扩容

==HashMap是非线程安全的==