【Java源码】集合类-JDK1.8 哈希表-红黑树-HashMap总结

JDK 1.8 HashMap是数组+链表+红黑树实现的，在阅读HashMap的源码之前先来回顾一下大学课本数据结构中的哈希表和红黑树。

什么是哈希表？

在存储结构中，关键值key通过一种关系f和唯一的存储位置相对应，关系f即哈希函数，Hash(k)=f(k)。按这个思想建立的表就是哈希表。

当有两个不相等的关键字key1和key2,但f(key1)=f(key2)这两个key地址相同，就发生了冲突现象。

冲突不能避免只能减少，通过设计均匀的哈希函数来减少。

常用哈希函数？ 1. 直接定址法

Hash(key) = a*key + b (a,b为常数)

取关键字的某种线性关系，实际中使用较少。

2. 初留余数法

Hash(key) = key mod p (p，整数)

即关键字key除以p的余数作为地址。

3.数字分析法，平方取中法，折叠法 处理冲突的方法？

处理冲突就是为这个关键字找到另一个空的哈希地址。

1.开放地址法

线性探测法

二次探测法

双哈希函数探测法

2.拉链法

拉链法的基本思想是，根据关键字k，将数据元素存放在哈希基表中的i=hash(k)位置上。如果产生冲突，则创建一个结点存放该数据元素，并将该结点插入到一个链表中。这种由冲突的数据元素构成的链表称为哈希链表。一个哈希基表与若干条哈希链表相连。

例如，对于如下的关键字序列：{9，9，24，44，32，86，36，3，62，56}
设哈希函数 hash(k) = k % 10，hash(k)对应哈希基表 table 的下标值 i，采用拉链法的哈希表结构如图:

红黑树

红黑树本质上就是一棵二叉查找树（二叉排序树），红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

什么是二叉查找树（二叉排序树）？

二叉查找树（Binary Search Tree）也就是二叉排序树。特征性质：

任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

左、右子树也为二叉查找树。

按中序遍历可以得到有序序列。

什么是红黑树？

维基百科定义：https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在log n时间内完成查找，插入和删除，这里的n是树中元素的数目。

特征性质：

节点是红色或黑色。

根结点是黑的。

所有叶子都是黑色（叶子是NIL节点）。

每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）

对于任一结点而言，其到叶结点的每一条路径都包含相同数目的黑结点

JDK 1.8 Map接口 public interface Map<K,V> { int size(); //返回Map中键值对的个数 boolean isEmpty(); //检查map是否为空 boolean containsKey(Object key); //查看map是否包含某个键 boolean containsValue(Object value); //查看map是否包含某个值 V put(K key, V value); //保存，若原来有这个key则覆盖并返回原来的值 V get(Object key); //根据key获取值, 若没找到，则返回null V remove(Object key); //根据key删除, 返回key原来的值，若不存在，则返回null void putAll(Map<? extends K, ? extends V> m); //将m中的所有键值对到当前的Map void clear(); //清空Map Set<K> keySet(); //返回Map中所有键 Collection<V> values(); //返回Map中所有值 Set<Map.Entry<K, V>> entrySet(); //返回Map中所有键值对 //内部接口，表示一个键值对 interface Entry<K,V> { K getKey(); //返回键 V getValue(); //返回值 V setValue(V value); //setvalue } } HashMap特点

根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

HashMap最多只允许一条记录的键为null，允许多条记录的值为null。

HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

负载因子可以修改，也可以大于1，建议不要轻易修改，除非特殊情况。

内部数据结构:

HashMap 类属性