1. Hashtable
1.1 定义
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
从源码中可以看到，Hashtable继承了Dictionary<K,V>，实现了Map<K,V>接口,其中Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。每个键和值都是一个对象，在任何一个 Dictionary 对象中，每个键最多与一个值相关联。Map是key-value键值接口。
Hashtable采用
链地址法实现哈希表，定义了几个重要的参数：table、count、threshold、loadFactor、modCount。
- table：是一个Entry[ ]数组，Entry代表了
拉链的节点。哈希表中的key-value键值对都是存储在Entry数组中的。 - count：hashtable的大小，他不是hashtable容量的大小，而是Entry键值对的数量。
- threshold：代表
阈值的意思，用于判断是否需要进行扩容，threshold=加载因子* 容量。 - loadFactory：加载因子，默认是0.75。
- modCount：用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常。
1.2 构造函数
- 无参构造函数，容量为11，加载因子为0.75。
public Hashtable() {
this(11, 0.75f);
}
- 指定初始容量和默认加载因子的构造函数
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
- 用指定初始容量和指定加载因子构造一个新的空哈希表。其中initHashSeedAsNeeded方法用于初始化hashSeed参数，其中hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算。这个hashSeed是一个与实例相关的随机值，主要用于解决hash冲突。
public Hashtable(int initialCapacity, float loadFactor) {
//验证初始容量
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity:"+ initialCapacity);
//验证加载因子
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
//初始化table，获得大小为initialCapacity的table数组
table = new Entry[initialCapacity];
//计算阀值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//初始化HashSeed值
initHashSeedAsNeeded(initialCapacity);
}
HashSeed的作用如下
private int hash(Object k) {
return hashSeed ^ k.hashCode();
}
- 构造一个与给定的 Map 具有相同映射关系的新哈希表。
public Hashtable(Map<? extends K, ? extends V> t) {
//设置table容器大小，其值==t.size * 2 + 1
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
1.3 主要方法
HashTable的API对外提供了许多方法，这些方法能够很好帮助我们操作HashTable，但是这里我只介绍两个最根本的方法：put、get。
put方法：将指定 key 映射到此哈希表中的指定 value。注意这里键key和值value都不可为空。
public synchronized V put(K key, V value) {
// 确保value不为null
if (value == null) {
throw new NullPointerException();
}
/*
* 确保key在table[]是不重复的
* 处理过程：
* 1、计算key的hash值，确认在table[]中的索引位置
* 2、迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值
*/
Entry tab[] = table;
int hash = hash(key); //计算key的hash值
int index = (hash & 0x7FFFFFFF) % tab.length; //确认该key的索引位置
//迭代，寻找该key，替换
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) { //如果容器中的元素数量已经达到阀值，则进行扩容操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 在索引位置处插入一个新的节点
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
//容器中元素+1
count++;
return null;
}
put的大致流程为：首先根据key计算hash值，通过hash值计算出key在table数组中的索引位置。如果该位置没有元素，那么就直接放入即可，反之就是计算出来的key具有哈希冲突，hashtable的做法是使用链表来解决哈希冲突。然后在遍历链表，如果发现链表存在这个key元素，那么直接替换原来的元素，否则在将改key-value节点插入该index索引位置处。
注意：
- Hashtable扩容：如果需要向table[]中添加Entry元素，会首先进行容量校验，如果容量已经达到了阀值，HashTable就会进行扩容处理rehash()，如下:
protected void rehash() {
int oldCapacity = table.length;
//元素
Entry<K,V>[] oldMap = table;
//新容量=旧容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
//新建一个size = newCapacity 的HashTable
Entry<K,V>[] newMap = new Entry[];
modCount++;
//重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//重新计算hashSeed
boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
//将原来的元素拷贝到新的HashTable中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
在这个rehash()方法中我们可以看到容量扩大两倍+1，同时需要将原来HashTable中的元素一一复制到新的HashTable中，这个过程是比较消耗时间的，同时还需要重新计算hashSeed的，毕竟容量已经变了。
- 在计算索引时（hash & 0x7FFFFFFF）与运算的作用？
0x7FFFFFFF是一个用16进制表示的整型,是整型里面的最大值。
转换成二进制：
0111 1111 1111 1111 1111 1111 1111 1111（前31一个1代表数值，在计算机中整型最高位（32位）是符号位 0代表正数，1代表负数）。为了解决hash为负数的情况，去掉符号位的作用。负数与其进行&操作将产生一个正整数。
get方法：
相对于put方法，get方法就会比较简单，处理过程就是计算key的hash值，判断在table数组中的索引位置，然后迭代链表，匹配直到找到相对应key的value,若没有找到返回null。
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
2. HashMap
2.1 定义
它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
2.2 数据结构
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。
这里需要讲明白两个问题：数据底层具体存储的是什么？这样的存储方式有什么优点呢？
一、从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。是HashMap的一个静态内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个圆点就是一个Node对象。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
二、 HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。假如向HashMap中添加一个元素：
map.put("美团","腾讯")；
首先就会根据美团先计算出hash值，然后再通过Hash算法的后两步运算（高位运算和取模运算）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：
int threshold; // 阈值，所能容纳的key-value对极限
final float loadFactor; // 负载因子
int modCount; /*用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。
强调一点，内部结构发生变化指的是结构发生变化，
例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。*/
int size; //HashMap中实际存在的键值对数量
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
这里存在一个问题就是负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树（还有另外一个限制：当发现链表中的元素个数大于8之后，还会判断一下当前数组的长度，如果数组长度小于64时，此时并不会转化为红黑树，而是进行扩容。只有当链表中的元素个数大于8，并且数组的长度大于等于64时才会将链表转为红黑树。），利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。当红黑树的元素小于等于6时，又会退化为链表结构(不一定小于6的时候转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换)。
退化为链表结构的原因：
当元素个数小于一个阈值时，链表整体的插入查询效率要高于红黑树，当元素个数大于此阈值(8)时，链表整体的插入查询效率要低于红黑树。
//转化为红黑树的最小的桶的大小
static final int MIN_TREEIFY_CAPACITY = 64;
//阈值
static final int TREEIFY_THRESHOLD = 8;
//退化链表的临界值
static final int UNTREEIFY_THRESHOLD = 6;
2.3 主要方法
HashMap的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。
- 确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):
方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样
return h & (length-1); //第三步 取模运算
}
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方(上文提到的)，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
下面举例说明下，n为table的长度。
-
分析HashMap的put方法
JDK1.8HashMap的put方法源码如下:
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤①：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③：节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤④：判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤⑤：该链为链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key,value,null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤⑥：超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
- 扩容机制
扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。
网友评论