此博客主要记录哈希表的具体原理，及常见的面试题目。
/-- Map: 双列数据，存储key-value 对的数据
/-- HashMap : 作为Map的主要实现类；线程不安全，效率高；存储null 的key 和value（1.2出现）
/-- LinkedHashMap: 保证在遍历map元素时，可以按照添加的顺序实现遍历 (1.4出现)
（原因： 在原有的HashMap底层结构的基础上，添加了一对指针，指向前一个和后一个元素。对于频繁遍历操作，此类执行效率高）
/-- TreeMap: 保证按照添加的key - value 对进行排序，实现排序遍历。此时考虑key 的自然排序（1.2出现）
底层实现红黑树
/-- Hashtable : 作为古老的实现类; 线程安全，效率低；不能存储null 的key 和value （1.0出现）
/-- Properties: 常用来处理配置文件。 key和value 都是String类型
HashMap的底层： 数组 + 链表 （jdk7 之前）
数组 + 链表 + 红黑树 （jdk 8）
map结构的理解：
Map中的key : 无序、不可重复，使用Set 储存所有的key ---> key 所在的类要重写 equals() 和 hashCode() (HashMap 为例)
Map中的value: 无序、可重复， 使用Collection存储所有的value ---> value 所在的类要重写equals()
Map中的entry : 无序、不可重复， 使用 Set 存储所有的entry
底层实现原理？ 以jdk 7 为例：
HashMap map = new HashMap();
在实例化以后， 底层创建了长度为16的一维数组 Entry[ ] table。
map. put(key1, value1);
首先，调用key1 所在类的hashCode() 计算key1 的哈希值， 此哈希值经过某种算法（可以想象为取模，源码上和（length - 1）进行 “与” 运算）以后，得到在Entry 数组中的存放位置。
如果此位置上的数据为空，则此时的entry(key1- value1) 添加成功。
如果此位置上的数据不为空，意味着此位置上存在一个或者多个数据（以链表的方式存在），比较key1和已经存在的一个或者多个数据的哈希值。
如果key1的哈希值与已经存在的哈希值都不相同，此时添加成功。
如果哈希值重复，继续比较equals（）。返回false则添加成功；返回true,则更新相同key 值的 value。
在不断添加的过程中，会涉及到扩容的问题，默认的扩容方式：扩容为原来的两倍，并将原有的数据复制过来。
吞吐临界值(或者叫阈值、threshold) 是负载因子（或者叫填充比）乘以哈希表底层数组长度。
（当size的长度大于或等于阈值（一般是0.75），并且插入的位置不是null (要插入进链表)，就要扩容，扩容为原来的两倍）
jdk 8 相较于jdk 7在底层实现方面的不同：
1. new HashMap() ： 底层没有创建一个长度为16的数组
2. jdk 8 底层数组是： Node[ ] , 而非 Entry [ ]
3. 首次调用put ( ) , 方法时，底层调用长度为16 的数组
4. jdk 7底层结构只有： 数组+ 链表， jdk 8 中底层结构： 数组 + 链表+ 红黑树。
当数组的某一个索引位置上的元素以链表的形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引上位置的所有数据改为使用红黑树存储。
DEFAULT_INITIAL_CAPACITY : HashMap 的默认容量， 16
EDFAULT＿LOAD_FACTOR : HashMap 的默认加载因子， 0.75
threshold : 扩容临界值， = 容量 * 填充因子 ， 16 * 0.75 = 12
TREEIFY_THRESHOLD : Bucket 中链表长度大于该默认值，转化为红黑树， ８
MIＮ＿TREEEIFY_CAPACITY : 桶中的Node 被树化时最小的hash 表容量， 64
1. HashMap 的底层实现原理 ？
2. HashMap 和HashTable 的区别 ？
3. CurrentHashMap 与 Hashtable 的异同？
原文：https://www.cnblogs.com/nobita/p/14956413.html