Hashtable、HashMap、TreeMap 分析

Hashtable、HashMap、TreeMap 区别

Hashtable、HashMap、TreeMap 都是最常见的一些 Map 实现，是以键值对的形式存储和操作数据的容器类型。

Hashtable

Hashtable 是早期 Java 类库提供的一个哈希表实现，本身是同步的，不支持 null 键和值，由 于同步导致的性能开销，所以已经很少被推荐使用。 初始化与增长方式

• 初始化时：HashTable在不指定容量的情况下的默认容量为11，且不要求底层数组的容量一 定要为2的整数次幂;HashMap默认容量为16，且要求容量一定为2的整数次幂。
• 扩容时：Hashtable将容量变为原来的2倍加1;HashMap扩容将容量变为原来的2倍。**

HashMap

HashMap 是应用更加广泛的哈希表实现，行为上大致上与 HashTable 一致，主要区别在于 HashMap 不是同步的，支持 null 键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个 用户 ID 和用户信息对应的运行时存储结构。

HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据 的不一致。如果需要同步：

1. 可以用 Collections的synchronizedMap方法;
2. 使用ConcurrentHashMap类，相较于HashTable锁住的是对象整体， ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式，然后给每一段数据分 配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性，而且性能上有 长足的提升。

TreeMap

TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、 remove 之类操作都是 O(log(n))的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。

HashMap原理

什么时候会使用HashMap，它有什么特点

它是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

HashMap的工作原理

通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

get和put的原理，equals()和hashCode()作用

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

hash的实现

在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

HashMap的大小超过了负载因子(load factor)定义的容量，如何解决

如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

HashMap一些约定

HashMap 的性能表现非常依赖于哈希码的有效性，比如:

• equals 相等，hashCode一定要相等;
• 重写了 hashCode 也要重写 equals;
• hashCode 需要保持一致性，状态改变返回的哈希值仍然要一致;
• equals 的对称、反射、传递等特性;

equals()特性

1. 等价关系
2. 自反性 x.equals(x); // true
3. 对称性 x.equals(y) == y.equals(x); // true
4. 传递性 if (x.equals(y) && y.equals(z)) x.equals(z); // true;
5. 一致性 多次调用 equals() 方法结果不变 x.equals(y) == x.equals(y); // true
6. 与 null 的比较 对任何不是 null 的对象 x 调用 x.equals(null) 结果都为 false x.equals(null); // false;

TreeMap原理

它是按照key的排序结果来组织内部结构的map类集合，改变map类散乱无序的现象。继承自abstractMap,它有两个与众不同的接口，SortedMap与NavigabableMap，SortedMap表示key有序不可重复，支持获取哦图为key-value元素，或者根据key指定范围获取子集集合。插入key必须实现camparable或者提供额外的比较器comparator,所以key不允许为null，但是value可以。NavigabableMap继承自SortedMap，根据搜索条件返回最匹配key-value。 不同于hashmap,treepmap并非一定要覆写hashcode和equals来达到key去重目的。

ConcurrentHashMap原理

什么是CAS

CAS：它是解决轻微冲突的多线程并发场景下使用锁造成性能损耗的一种机制，cas它是先比较，如果不符合预期，则进行重试，包含三个重要的操作要素：内存位置，预期原值与新值。 如果内存位置的值与预期原值相等，则处理器将该位置值更新为新值，如果不相等，则获取当前值，然后进行不断的轮询操作直到成果达到某个阙值退出。

早期版本ConcurrentHashMap

早期 ConcurrentHashMap，其实现是基于:

• 分离锁，也就是将内部进行分段(Segment)，里面则是 HashEntry 的数组，和 HashMap 类似，哈希相同的条目也是以链表形式存放。
• HashEntry 内部使用 volatile 的 value 字段来保证可见性，也利用了不可变对象的机制以改 进利用 Unsafe 提供的底层能力，比如volatile access，去直接完成部分操作，以最优化性 能，毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。

JDK11中的ConcurrentHashMap

在JDK11中，它改造了三点：

• 取消分段锁机制（Segment），进一步降低冲突概率;
• 引入红黑树解构，同一个哈希槽元素个数超过一定的阙值后，单链表转化成红黑树;
• 使用了更加优化方式统计集合内的元素数量。原来map原有的size方法最大只能表达2的31次方减一，现在额外提供mappingCount方法，最大表示为2的63次方减一，当元素更新时，使用多种优化和CAS提高并发能力;
• 其内部仍然有 Segment 定义，但仅仅是为了保证序列化时的兼容性而已，不再有任何结构 上的用处。因为不再使用 Segment，初始化操作大大简化，修改为 lazy-load 形式，这样可以有效避免 初始开销，解决了老版本很多人抱怨的这一点;
• 数据存储利用 volatile 来保证可见性;
• 使用 CAS 等操作，在特定场景进行无锁并发操作;
• 使用 Unsafe、LongAdder 之类底层手段，进行极端情况的优化;

更多细节实现通过使用 Unsafe 进行了优化，例如 tabAt 就是直接利用 getObjectAcquire，避免间接调用的开销。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);

} table长度为64，数据存储结构分为两种，链表与红黑树，当某个槽内元素个数增加到超过8个且table容量大于或等于64，由链表转化成红黑树。当某个槽内元素减少到6个，又由红黑树转化成链表。当table小于63时，只会扩容，不会转化成红黑树。

转化过程使用同步块锁住当前槽首元素，防止其他进程对当前槽进行增删改操作，转换完成，通过CAS替换原有链表。因为TreeNode节点也存储next引用，所以只需从TreeBin的first元素开始遍历所有节点，并把节点从TreeCode类型转化为Node类型即可，当构造好新链表之后，会用CAS替换原有的红黑树。