map

ConcurrentHashMap

jdk7中： 数据结构：ReentranLock+Segment+HashEntry。一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 又是一个链表结构。 元素查询：查询时进行了2次 hash。第一次 hash 定位到 Segment，第二个 hash 定位到元素所在链表的头 锁：Segment 继承了 ReentrantLock，并发时锁定操作的 Segment，其他 Segment 不受影响。并发度等于 Segment 个数，可以通过构造函数指定，数组扩容不会影响其他的 Segment. get：无需加锁，使用 volatile 保证

HashMap 和 HashTable

异同

• HashTable 是线程安全的，所以单线程情况下性能没有 HashMap 高。不接受 null 键值。HashMap 是线程不安全的，可接受 null 键值

• 随着长时间的使用 HashMap 不能保证其中元素的顺序不变

  HashTable

  是线程安全的 ，不过现在不常用。

  HashMap

• 底层由数组 + 链表实现。当数组长度超过64，链表高度超过8，则链表转变为红黑树，元素以内部类 Node 节点存在

• 数组下标的计算方法：计算 key 的 hash 值，二次 hash 然后对数组长度取模

• 如果没有 hash 冲突则创建 Node 插入数组

• 如果出现 hash 冲突则调用 equals 方法，相同则覆盖原数据，不同则在该元素上插入链表。当数组长度超过64，链表高度到8则链表转变为红黑树。链表高度低于6还会从红黑树降级为链表

• key = null 的节点存在下标是 0 的位置