HashMap && Hashtable浅析 | Lanourain's blog

HashMap

以哈希表为基础的Map实现，线程不安全，允许key或value为null，不保证顺序。和Hashtable类似，但是Hashtable线程安全且不可放入null。

interface Map

key-Value映射的集合接口，每个元素都包含一对Key对象和Value对象。在Map中，Key唯一，每个Key都有其对应的value值。该接口定义了一些Map应该包含的基本方法。

size()：返回包含的key-value映射数。
isEmpty()：Map中是否包含kv映射。
containsKey(Object key)：判断Key是否存在
containsValue(Object value)：判断value是否存在
get(Object key)：获取Key对应的Value
put(K key, V value)：存入Key-Value映射，如果key存在，则覆盖原Value。
remove(Object key)：删除对应的Key以及其Value映射。
Set keySet()：获取所有Key的集合
Collection values()：获取所有Value的集合
Set> entrySet()：返回Map的KV映射集合
interface Entry：Map的映射接口（KV映射），提供基本的get、set key-value的方法，以及根据key或者value进行排序的方法。

abstract class AbstractMap implements Map

提供了Map的骨架（skeletal）实现，减小了实现Map接口的代价。类似AbstractCollection，基本的实现方法可能复杂度会有点高，所有很多Map的具体实现类都会自己实现相应方法降低复杂度。

containsValue，containsKey：使用迭代器迭代entrySet()进行查找，复杂度O(N)。
get(Object key), remove(Object key)：迭代器迭代entrySet()查找对应映射实例，复杂度O(N)

class HashMap extends AbstractMap implements Map, Cloneable, Serializable

KV存储，HashMap内部使用哈希 + 数组 + 链表的形式来存储数据。

Node[] table，数组的index = hash(key)，table[hash(key))] = 对应节点链表。
节点：Node implements Map.Entry，包含4个属性，实现了Entry的一些基本方法：

int hash;       // key转换的hash值，数组的index
K key;          // 实际的key
V value;        // 实际的value
Node<K,V> next; // 使用链表法解决hash冲突，所以每个节点需要记录后续节点

扩容，如果当前table的存储容量超过阀值（threshold（table包含元素阀值） = capacity（table总长度） * load_factor（加载因子，元素可占总容量的百分比最大值）），则会进行扩容，容量扩大为原来的两倍，然后将老的数据遍历一遍在放入到新的table中，所以如果可以估计容量的话，初始化hashMap时设置容量会比较好。

存储KV对，将key转换成hash，放入到table[hash]链表的最后，为了防止hash表蜕变为链表（所有数据都在一个链表节点上），当单个节点上链表长度超过8时，会将链表转换成红黑树来加快查询效率（FIXME后续开篇讲红黑树）。

根据Key获取value，将key转换成hash值，遍历对应节点（table的长度控制在2的n次方，通过位运算快速取模）上的链表数据，找到实际key相等的节点返回其value。

遍历，HashMap提供的遍历KeySet或ValueSet或EntrySet，都是使用内部实现的一个HashIterator来实现迭代遍历。

参考

HashMap源码解析（JDK8）

Hashtable

和Hashmap类型，基于hash的Map实现，kv都不可放入null，线程安全。

abstract class Dictionary

Map接口的前身，已弃用。

class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable

Hashtable 偏向于hashmap的线程安全前身，后续拆分出了线程不安全但是速度快的hashmap + 线程安全的ConcurrentHashMap，该类继承的接口（Dictionary）、迭代器等都有新的替代接口类替代。
内部原理基本和HashMap一致，只是使用了synchronized来保证线程安全。