hash存储机制

Hash存储机制


目录
1 HASH存储 1
1.1 HASH存储 1
1.2 集合和引用 1
2 HASHMAP 1
2.1 HASHMAP存储实现 1
2.2 HASHMAP代码实现 2
3 HASHSET 9
3.1 HASHSET代码实现 9
3.2 HASHMAP的PUT与HASHSET的ADD 11



1 Hash存储
1.1 Hash存储
HashMap 和HashSet 是Java Collection Framework 的两个重要成员,其中HashMap是Map 接口的常用实现类，HashSet 是Set 接口的常用实现类。虽然HashMap 和HashSet实现的接口规范不同，但它们底层的Hash 存储机制完全一样，甚至HashSet 本身就采用HashMap 来实现的.通过HashMap、HashSet 的源代码分析其Hash 存储机制.
1.2 集合和引用
就像引用类型的数组一样,当我们把Java 对象放入数组之时,并不是真正的把Java 对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是一个引用变量。
实际上,HashSet 和HashMap 之间有很多相似之处，对于HashSet 而言，系统采用Hash 算法决定集合元素的存储位置,这样可以保证能快速存取集合元素；对于HashMap 而言,系统key-value 当成一个整体进行处理，系统总是根据Hash 算法来计算key-value 的存储位置，这样可以保证能快速存取Map 的key-value 对。
在介绍集合存储之前需要指出一点：虽然集合号称存储的是Java 对象，但实际上并不会真正将Java 对象放入Set 集合中，只是在Set 集合中保留这些对象的引用而言。也就是说：Java 集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的Java 对象。

2 HashMap
2.1 HashMap存储实现
要知道hashmap是什么，首先要搞清楚它的数据结构，在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“散列存储“），请看下图：横排表示数组，纵排表示数组元素（实际上是一个链表结构）。




从图中看出一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组，而每个数组元素对应的是一个链表引用。
往hashmap中put元素：
① 先根据key的hash值得到这个元素在数组中的位置（即下标），然后把这个元素放到对应的位置中了。
② 如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。
从hashmap中get元素：
① 首先计算key的hashcode，找到数组中对应位置的某一元素；
② 然后通过key的equals方法在对应位置的链表中找到需要的元素。
从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的。

2.2 HashMap代码实现
当程序试图将多个key-value 放入HashMap 中时，以如下代码片段为例：

HashMap<String , Double> map = new HashMap<String , Double>();
map.put("语文" , 80.0);
map.put("数学" , 89.0);
map.put("英语" , 78.2);

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。
当程序执行map.put("语文" , 80.0)时, 系统将调用"语文" 的hashCode()方法得到其hashCode 值——每个Java 对象都有hashCode()方法，都可通过该方法获得它的hashCode值.得到这个对象的hashCode 值之后,系统会根据hashCode 值来决定该元素的存储位置.
我们可以看HashMap 类的put(K key , V value) 方法的源代码：

public V put(K key, V value) {
// 如果key 为null，调用putForNullKey 方法进行处理
if (key == null) return putForNullKey(value);
// 根据key 的keyCode 计算Hash 值
int hash = hash(key.hashCode());
// 搜索指定hash 值在对应table 中的索引
int i = indexFor(hash, table.length);
// 如果i 索引处的Entry 不为null,通过循环不断遍历e 元素的下一个元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;	
// 找到指定key 与需要放入的key 相等（hash 值相同通过equals 比较放回true）
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
} }	
// 如果i 索引处的Entry 为null，表明此处还没有Entry
modCount++;
// 将key、value 添加到i 索引处
addEntry(hash, key, value, i);
return null;
}

上面程序中用到了一个重要的内部接口:Map.Entry，每个Map.Entry 其实就是一个key-value 对。从上面程序中可以看出：当系统决定存储HashMap 中的key-value 对时，完全没有考虑Entry 中的value，仅仅只是根据key 来计算并决定每个Entry 的存储位置。这也说明了前面的结论：我们完全可以把Map 集合中的value 当成key 的附属，当系统决定了key 的存储位置之后，value 随之保存在那里即可。
上面方法提供了一个根据hashCode() 返回值来计算Hash 码的方法：hash()，这个方法
是一个纯粹的数学计算，其方法如下：

static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

对于任意给定的对象，只要它的hashCode() 返回值相同，那么程序调用hash(int h) 方法所计算得到的Hash 码值总是相同的。接下来程序会调用indexFor(int h, int length)方法来计算该对象应该保存在table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

static int indexFor(int h, int length) {
return h & (length-1);
}

这个方法非常巧妙，它总是通过h &(table.length -1) 来得到该对象的保存位置——而HashMap 底层数组的长度总是2 的n 次方，这一点可参看后面关于HashMap 构造器的介绍。
当length 总是2 的倍数时， h & (length-1) 将是一个非常巧妙的设计： 假设h=5,length=16, 那么h & length - 1 将得到5；如果h=6,length=16, 那么h & length - 1将得到6 ……如果h=15,length=16, 那么h & length - 1 将得到15；但是当h=16 时,length=16 时，那么h & length - 1 将得到0 了；当h=17 时, length=16 时，那么h &length - 1 将得到1 了……这样保证计算得到的索引值总是位于table 数组的索引之内。
根据上面put 方法的源代码可以看出，当程序试图将一个key-value 对放入HashMap中时，程序首先根据该key 的hashCode() 返回值决定该Entry 的存储位置：如果两个Entry 的key 的hashCode() 返回值相同，那它们的存储位置相同。如果这两个Entry 的key 通过equals 比较返回true，新添加Entry 的value 将覆盖集合中原有Entry 的value，但key 不会覆盖。如果这两个Entry 的key 通过equals 比较返回false，新添加的Entry 将与集合中原有Entry 形成Entry 链，而且新添加的Entry 位于Entry链的头部——具体说明继续看addEntry() 方法的说明。
当向HashMap 中添加key-value 对，由其key 的hashCode() 返回值决定该keyvalue对（就是Entry 对象）的存储位置。当两个Entry 对象的key 的hashCode() 返回值相同时，将由key 通过eqauls() 比较值决定是采用覆盖行为（返回true），还是产生Entry 链（返回false）。
上面程序中还调用了addEntry(hash, key, value, i); 代码，其中addEntry 是HashMap提供的一个包访问权限的方法，该方法仅用于添加一个key-value 对.下面是该方法的代码：

void addEntry(int hash, K key, V value, int bucketIndex) {
// 获取指定bucketIndex 索引处的Entry
Entry<K,V> e = table[bucketIndex]; // ①
//将新创建的Entry 放入bucketIndex 索引处，并让新的Entry 指向原来的Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 如果Map 中的key-value 对的数量超过了极限
if (size++ >= threshold)
// 把table 对象的长度扩充到2 倍。
resize(2 * table.length); // ②
}

上面方法的代码很简单，但其中包含了一个非常优雅的设计：系统总是将新添加的Entry对象放入table 数组的bucketIndex 索引处——如果bucketIndex 索引处已经有了一个Entry 对象，那新添加的Entry 对象指向原有的Entry 对象（产生一个Entry 链），如果bucketIndex 索引处没有Entry 对象，也就是上面程序①号代码的e 变量是null，也就是新放入的Entry 对象指向null，也就是没有产生Entry 链。
Hash 算法的性能选项
根据上面代码可以看出，在同一个bucket 存储Entry 链的情况下，新放入的Entry 总是位于bucket 中，而最早放入该bucket 中的Entry 则位于这个Entry 链的最末端。
上面程序中还有这样两个变量：
* size：该变量保存了该HashMap 中所包含的key-value 对的数量。
* threshold：该变量包含了HashMap 能容纳的key-value 对的极限，它的值等于HashMap 的容量乘以负载因子（load factor）。
从上面程序中②号代码可以看出，当size++ >= threshold 时，HashMap 会自动调用resize 方法扩充HashMap 的容量。每扩充一次，HashMap 的容量就增大一倍。
上面程序中使用的table 其实就是一个普通数组，每个数组都有一个固定的长度，这个数
组的长度就是HashMap 的容量。HashMap 包含如下几个构造器：
* HashMap()：构建一个初始容量为16，负载因子为0.75 的HashMap。
* HashMap(int initialCapacity)：构建一个初始容量为initialCapacity，负载因子为0.75 的HashMap。
* HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个HashMap。
当创建一个HashMap 时，系统会自动创建一个table 数组来保存HashMap 中的Entry，下面是HashMap 中一个构造器的代码：

// 以指定初始化容量、负载因子创建HashMap
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能为负数
if (initialCapacity < 0)
throw new IllegalArgumentException( "Illegal initial capacity: " + initialCapacity);
// 如果初始容量大于最大容量，让出示容量
if (initialCapacity >MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;
// 负载因子必须大于0 的数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(loadFactor);
// 计算出大于initialCapacity 的最小的2 的n 次方值。
int capacity = 1;
while (capacity < initialCapacity) capacity <<= 1;
this.loadFactor = loadFactor;
// 设置容量极限等于容量* 负载因子
threshold = (int)(capacity * loadFactor);
// 初始化table 数组
table = new Entry[capacity]; // ①
init();
}

上面代码中粗体字代码包含了一个简洁的代码实现：找出大于initialCapacity 的、最小的
2 的n 次方值，并将其作为HashMap 的实际容量（由capacity 变量保存）。例如给定
initialCapacity 为10，那么该HashMap 的实际容量就是16。
initialCapacity 与HashTable 的容量创建HashMap 时指定的initialCapacity 并不等于HashMap 的实际容量，通常来说，HashMap 的实际容量总比initialCapacity 大一些，除非我们指定的initialCapacity 参数值恰好是2 的n 次方。当然，掌握了HashMap 容量分配的知识之后，应该在创建HashMap 时将initialCapacity 参数值指定为2 的n 次方，这样可以减少系统的计算开销。
程序①号代码处可以看到：table 的实质就是一个数组，一个长度为capacity 的数组。
对于HashMap 及其子类而言，它们采用Hash 算法来决定集合中元素的存储位置。当系统开始初始化HashMap 时，系统会创建一个长度为capacity 的Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个bucket 都有其指定索引，系统可以根据其索引快速访问该bucket 里存储的元素。
无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个Entry），由于Entry 对象可以包含一个引用变量（就是Entry 构造器的的最后一个参数）用于指向下一个Entry，因此可能出现的情况是：HashMap 的bucket 中只有一个Entry，但这个Entry 指向另一个Entry ——这就形成了一个Entry 链。HashMap 的读取实现.
当HashMap 的每个bucket 里存储的Entry 只是单个Entry ——也就是没有通过指针产生Entry 链时，此时的HashMap 具有最好的性能：当程序通过key 取出对应value时，系统只要先计算出该key 的hashCode() 返回值，在根据该hashCode 返回值找出该key 在table 数组中的索引，然后取出该索引处的Entry，最后返回该key 对应的value 即可。看HashMap 类的get(K key) 方法代码：

public V get(Object key) {
// 如果key 是null，调用getForNullKey 取出对应的value
if (key == null)
return getForNullKey();
// 根据该key 的hashCode 值计算它的hash 码
int hash = hash(key.hashCode());
// 直接取出table 数组中指定索引处的值，
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
// 搜索该Entry 链的下一个Entry
e = e.next)
// ① {
Object k;
// 如果该Entry 的key 与被搜索key 相同
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

从上面代码中可以看出，如果HashMap 的每个bucket 里只有一个Entry 时，
HashMap 可以根据索引、快速地取出该bucket 里的Entry；在发生“Hash 冲突”的情况下，单个bucket 里存储的不是一个Entry，而是一个Entry 链，系统只能必须按顺序遍历每个Entry，直到找到想搜索的Entry 为止——如果恰好要搜索的Entry 位于该Entry 链的最末端（该Entry 是最早放入该bucket 中），那系统必须循环到最后才能找到该元素。
归纳起来简单地说，HashMap 在底层将key-value 当成一个整体进行处理，这个整体就是一个Entry 对象。HashMap 底层采用一个Entry[] 数组来保存所有的key-value对，当需要存储一个Entry 对象时，会根据Hash 算法来决定其存储位置；当需要取出一个Entry 时，也会根据Hash 算法找到其存储位置，直接取出该Entry。由此可见：HashMap 之所以能快速存、取它所包含的Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。当创建HashMap 时，有一个默认的负载因子（load factor），其默认值为0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少Hash 表（就是那个Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的
get() 与put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加Hash
表所占用的内存空间。
掌握了上面知识之后，我们可以在创建HashMap 时根据实际需要适当地调整loadfactor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。如果开始就知道HashMap 会保存多个key-value 对，可以在创建时就使用较大的初始化容量，如果HashMap 中Entry 的数量一直不会超过极限容量（capacity * load
factor）， HashMap 就无需调用resize() 方法重新分配table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为capacity的Entry 数组），因此创建HashMap 时初始化容量设置也需要小心对待。

3 HashSet
3.1 HashSet代码实现
对于HashSet 而言，它是基于HashMap 实现的，HashSet 底层采用HashMap 来保存所有元素，因此HashSet 的实现比较简单，查看HashSet 的源代码，可以看到如下代码：

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
// 使用HashMap 的key 保存HashSet 中所有元素
private transient HashMap<E,Object> map;
// 定义一个虚拟的Object 对象作为HashMap 的value
private static final Object PRESENT = new Object();
...
// 初始化HashSet，底层会初始化一个HashMap
public HashSet() {
map = new HashMap<E,Object>();
}
// 以指定的initialCapacity、loadFactor 创建HashSet
// 其实就是以相应的参数创建HashMap
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity , loadFactor);
}
// 调用map 的keySet 来返回所有的key
public Iterator<E> iterator() {
return map.keySet().iterator();
}
// 调用HashMap 的size() 方法返回Entry 的数量，就得到该Set 里元素的个数
public int size() {
return map.size();
}
// 调用HashMap 的isEmpty() 判断该HashSet 是否为空，
// 当HashMap 为空时，对应的HashSet 也为空
public boolean isEmpty() {
return map.isEmpty();
}
// 调用HashMap 的containsKey 判断是否包含指定key
//HashSet 的所有元素就是通过HashMap 的key 来保存的
public boolean contains(Object o) {
return map.containsKey(o);
}
// 将指定元素放入HashSet 中，也就是将该元素作为key 放入HashMap
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
// 调用HashMap 的remove 方法删除指定Entry，也就删除了HashSet 中对应的元素
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
// 调用Map 的clear 方法清空所有Entry，也就清空了HashSet 中所有元素
public void clear() {
map.clear();
}
...
}

由上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个HashMap对象来存储所有的集合元素，所有放入HashSet 中的集合元素实际上由HashMap 的key来保存，而HashMap 的value 则存储了一个PRESENT，它是一个静态的Object 对象。
HashSet 的绝大部分方法都是通过调用HashMap 的方法来实现的，因此HashSet 和HashMap 两个集合在实现本质上是相同的。

3.2 HashMap的put与HashSet的add
由于HashSet 的add() 方法添加集合元素时实际上转变为调用HashMap 的put() 方法来添加key-value 对，当新放入HashMap 的Entry 中key 与集合中原有Entry 的key 相同（hashCode() 返回值相等，通过equals 比较也返回true），新添加的Entry 的value 将覆盖原来Entry 的value，但key 不会有任何改变，因此如果向HashSet 中添加一个已经存在的元素，新添加的集合元素（底层由HashMap 的key 保存）不会覆盖已有的集合元素。
掌握上面理论知识之后，接下来看一个示例程序，测试一下自己是否真正掌握了HashMap和HashSet 集合的功能。

class Name {
private String first;
private String last;
public Name(String first, String last) {
this.first = first;
this.last = last;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first) && n.last.equals(last);
}
return false;
}
}
public class HashSetTest {
public static void main(String[] args) {
Set<Name> s = new HashSet<Name>();
s.add(new Name("abc", "123"));
System.out.println(s.contains(new Name("abc", "123")));
}
}

上面程序中向HashSet 里添加了一个new Name("abc", "123") 对象之后，立即通过程序判断该HashSet 是否包含一个new Name("abc", "123") 对象。粗看上去，很容易以为该程序会输出true。实际运行上面程序将看到程序输出false，这是因为HashSet 判断两个对象相等的标准除了要求通过equals() 方法比较返回true 之外，还要求两个对象的hashCode() 返回值相等。而上面程序没有重写Name 类的hashCode() 方法，两个Name 对象的hashCode() 返回值并不相同，因此HashSet 会把它们当成2 个对象处理，因此程序返回false。
由此可见，当我们试图把某个类的对象当成HashMap 的key，或试图将这个类的对象放入HashSet 中保存时，重写该类的equals(Object obj) 方法和hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的hashCode() 返回值相同时，它们通过equals() 方法比较也应该返回true。通常来说，所有参与计算hashCode()返回值的关键属性，都应该用于作为equals() 比较的标准。hashCode() 和equals()
如下程序就正确重写了Name 类的hashCode() 和equals() 方法，程序如下：

class Name {
private String first;
private String last;
public Name(String first, String last) {
this.first = first;
this.last = last;
}
// 根据first 判断两个Name 是否相等
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first);
}
return false;
}
// 根据first 计算Name 对象的hashCode() 返回值
public int hashCode() {
return first.hashCode();
}
public String toString() {
return "Name[first=" + first + ", last=" + last + "]";
}
}
public class HashSetTest2 {
public static void main(String[] args) {
HashSet<Name> set = new HashSet<Name>();
set.add(new Name("abc" , "123"));
set.add(new Name("abc" , "456"));
System.out.println(set);
}
}

上面程序中提供了一个Name 类，该Name 类重写了equals() 和toString() 两个方法，这两个方法都是根据Name 类的first 实例变量来判断的，当两个Name 对象的first 实例变量相等时，这两个Name 对象的hashCode() 返回值也相同，通过equals()比较也会返回true。
程序主方法先将第一个Name 对象添加到HashSet 中，该Name 对象的first 实例变量值为"abc" ， ___________接着程序再次试图将一个first 为"abc" 的Name 对象添加到HashSet 中，很明显，此时没法将新的Name 对象添加到该HashSet 中，因为此处试图添加的Name 对象的first 也是" abc"，HashSet 会判断此处新增的Name 对象与原有的Name 对象相同，因此无法添加进入，程序在①号代码处输出set 集合时将看到该集合里只包含一个Name 对象，就是第一个、last 为"123"的Name 对象。__