前言：看了《Java编程思想》第十七章容器的深入研究中讲散列和散列码这一节，内容十分精彩。现根据该书内容加以自己的描述认真总结一下，其中很多内容直接搬运自于书中，例子是以Map为例展开的，这里分享给大家。
我们知道Map是保存每一条记录的是键值对<key,value>的形式,要查询value只要知道key就可以了value=map.get(key)。我们是如何快速实现查找的呢？假设我们自己实现一个MyMap类来实现键值关联的这种数据
Object[][] pairs = new Object[n][2];实现这样的结构，第i个元素的key = pairs[i][0];value = pairs[i][1];在我们根据key查找value时需要先查找key的位置，由于key在数组中是随机存储的，所以查找key是一个线性搜索过程，的平均时间复杂度将会是O(n)。另外存在一个显著的问题就是数组的长度是固定的，这很不灵活。List<K> keys = new ArrayList<K>();List<V> values = new ArrayList<V>();这样我们就可以用value = values.get(keys.indexOf(key));来访问，这虽然解决了数组长度固定的问题，但是查找key的位置复杂度依然是O(n)。看来查询速度瓶颈位于键的查询，而HashMap的查找时间复杂度是O(1)。这是怎么做到的呢？原因是HashMap使用了散列。
散列将键的信息通过散列函数映射到数组的索引中，以便能够实现快速的查找。
我们知道Map中的key是一个Object(称作键对象)，首先我们通过键对象生成一个整数，将其作为数组的下标，这个数字就是散列码。这个散列码是通过Object根类的public native int hashCode();方法产生，所以所有的类都可以产生散列码。通常在实现类中我们会根据需要覆盖此方法，实现我们自己的计算方式。
存储 当我们要向Map中存入一个Entry<key,value>时，我们首先根据它的键对象计算出对应的散列码，并将该Entry<key,value>存到数组对应于散列码的索引位置。当然不同的Entry<key,value>的key计算出的散列码可能是相同的，这就相当于在数组的同一个位置存入了多个Entry<key,value>，重复了如之奈何？不必担心，后面继续说明。
查找 查找时我们根据提供的键对象key用散列函数计算出它在数组中对应的索引位置，再在索引位置保存的多个对象中进行一次线性查询（通过equals()方法比较两个对象key是否相等）找到该key对应的value。
从查找的过程看我们通过计算散列码找到索引位置后进行了一次线性搜索，并通过equals()方法精确定位到了我们要找的Entry<key,value>，所以散列码是可以重复的，即我们的同一个散列码可以对应多个key。这样我们既解决了数组长度固定的问题，又解决了查询速度问题。
形象的比喻 其实我们可以把保存对象的数组索引看做是n=array.length个槽位(或者叫桶),在保存的时候我们根据计算哈希函数将分配到了不同的槽位中，每个槽位的数据条数相比于集合数据总条数很少，这样在找到槽位进行接下来的线性搜索只对很少的部分进行线性搜索，这就是查询速度如此之快的原因。
总结 散列码不需要是唯一的，但是通过hashCode()和equals()必须能够完全确定对象身份。对于散列函数的设计我们值的注意的是：
声明：下面两段代码来自《Java编程思想》,只在main函数测试中稍作了修改。
Map里面保存的都是关联对象，这样<键对象,值对象>一组在Java中有一个Entry接口，我们定义自己的MapEntry实现该接口，并实现其中的getKey(),getValue(),setValue()方法。从2.2中可知，我们必须覆盖Object根类的hashCode()和equals()方法，以完成我们自己的散列码计算和相等比较。
import java.util.Map.Entry;
public class MapEntry<K, V> implements Entry<K, V> {
private K key;
private V value;
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V v) {
V result = value;
value = v;
return result;
}
@Override
public int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
@Override
public boolean equals(Object o) {
if (!(o instanceof MapEntry)) {
return false;
}
MapEntry me = (MapEntry) o;
return (key == null ? me.getKey() == null : key.equals(me.getKey()))
&& (value == null ? me.getValue() == null : value.equals(me
.getValue()));
}
@Override
public String toString() {
return key + "=" + value;
}
}设计好了我们要在Map中保存的关联对象，我们就可以编写一个简单的SimpleHashMap来实际体会一下。详细解释在代码注释中。
import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
static final int SIZE = 997; // 选一个质数作为槽位数
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE]; //初始化该数组
public V put(K key, V value) {
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE; // 计算index
if (buckets[index] == null) { // 如果此槽位还是空的就初始化
buckets[index] = new LinkedList<MapEntry<K, V>>();
}
LinkedList<MapEntry<K, V>> bucket = buckets[index]; // 得到该槽位的数据List
MapEntry<K, V> pair = new MapEntry<K, V>(key, value); // 初始化一个MapEntry
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator(); // 获取List的迭代器
while (it.hasNext()) { // 遍历该槽位的list
MapEntry<K, V> iPair = it.next();
if (iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair); // 如果找到就替换原值
found = true; // 设置找到标记为true
break; // 退出循环
}
}
if (!found) { // 如果没找到，直接将该值添加到该槽位
buckets[index].add(pair);
}
return oldValue; // 返回旧值，如果原来没有这里返回的就是null
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE; // 计算index
if (buckets[index] == null) { // 如果该槽位为空，则找不到返回null
return null;
}
for (MapEntry<K, V> iPair : buckets[index]) {// 不为空则遍历槽位列表
if (iPair.getKey().equals(key)) {//如果找到
return iPair.getValue();//返回该值
}
}
return null;// 找不到返回 null
}
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null)
continue;
for (MapEntry<K, V> mpair : bucket) {
set.add(mpair);
}
}
return set;
}
public static void main(String[] args) {
SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
m.put("山东","济南");
m.put("四川", "成都");
m.put("甘肃", "兰州");
m.put("江苏", "南京");
System.out.println(m);
System.out.println(m.get("四川"));
System.out.println(m.entrySet());
}
}我们已经按照散列的思想实现了HashMap中的put()和get()，其实该例子中entrySet()方法依然是采用的线性搜索，这里不考虑该方法的效率问题。
接下来我们来看一下Java中HashMap源码，体会一下他是怎么实现的呢。
该类中首先定义了5个全局常量：
// 默认初始容量16，必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，必须是2的幂，且最大为 1<<30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;接着定义了一个内部类static class Node<K,V> implements Map.Entry<K,V>作为要保存键值节点，接着定义了几个静态工具方法。
接着就是该类的成员字段了：
/**存储数据的容器，该表在首次使用时初始化，并根据需要调整大小。长度始终是2的幂。*/
transient Node<K,V>[] table;
/**保存根据Map获取的Set集合*/
transient Set<Map.Entry<K,V>> entrySet;
/**Map中当前存储的键值对个数*/
transient int size;
/**此HashMap经过结构修改的次数结构修改是指更改HashMap 中映射数量或以其他方式修
改其内部结构（例如，再散列）的修改。 此字段用于在HashMap的Collection-views上
快速生成迭代器。*/
transient int modCount;
/**自动扩容阈值(threshold = capacity*loadFactor)， capacity是当前桶位数，loadFactor是负载因
子，默认0.75f;也就是当HashMap数据条数达到桶位数的75%时，就会自动扩容*/
int threshold;
/** 负载因子(默认0.75f), loadFactor = size/capacity */
final float loadFactor;当负载情况达到负载因子水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重新将现有对象分布到新的桶位中（这被称为再散列）。
public HashMap() // 构造一个空的HashMap
public HashMap(int initialCapacity) // 构造一个指定初始桶位数的HashMap
public HashMap(int initialCapacity, float loadFactor) // 同时指定桶位数和负载因子
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) // 用已有的Map构造一个HashMap接下来我们就跟着HashMap中的put()方法，顺藤摸瓜看一看HashMap是怎样计算散列码的和怎样保存的。最后我们看一下get()方法，和entrySet()，以对比我们实现的SimpleHashMap和Java本身的HashMap的差距。
首先看一下put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}该方法直接return了putVal()的返回值，putVal第一个参数用hash()工具方法生成散列值：
static final int hash(Object key) {
int h;
/*如果key为空，则返回hash值为0；否则计算当前键对象的hashCode()
（该hashCode()方法一般被我们覆盖过)，接着该值与他无符号右移
16位的结果按位与运算,返回该结果*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}下面看看putVal()中的详细情况：
/**
* @param hash key的散列值
* @param key 键对象
* @param value 要保存的值对象
* @param onlyIfAbsent 如果为true,不要替换存在的值对象
* @param evict 如果为false，则表处于创建模式
* @return 返回旧值，如果不存在返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// tab是桶位数组，p是某个桶位的根结点
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) // 如果为空或长度为0
n = (tab = resize()).length; // resize()并返回数组长度
if ((p = tab[i = (n - 1) & hash]) == null) // 如果该hash值对应的索引处为空
tab[i] = newNode(hash, key, value, null); // 初始化一个结点
else { // 否则不为空
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// p是树结构结点的话，就将其转成TreeNode执行putTreeVal()，插入结点
// 实际HashMap中还定义了个TreeNode的内部类，也就是说该槽位节点时一个树的根结点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // 在该槽位一直向下找，直到桶位的next为空,证明元素不存在
p.next = newNode(hash, key, value, null); // 初始化一个结点
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //
break;
}
// 如果找到了已经存在，就不添加直接跳出循环
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 存在映射了
V oldValue = e.value;
// 如果onlyIfAbsent为true或者oldValue为空则替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue; // 返回oldValue
}
}
++modCount;// HashMap结构修改计数加1
if (++size > threshold) // 如果此时保存的键值对数量超过了阈值
resize(); // 再散列
afterNodeInsertion(evict);
return null;
}putVal()方法涉及到调用其他众多方法，这里不再追查了。从putVal()方法中我们获得了很多信息，从编码风格上源码中似乎喜欢比较简洁的写法，比如像if ((tab = table) == null || (n = tab.length) == 0)或p = tab[i = (n - 1) & hash]等等，喜欢直接把tab,n,i初始化揉在判断课索引里。还有个特点是喜欢灵活使用for循环,像for (int binCount = 0; ; ++binCount)或for(;;)这种。另外我们的保存数据的容器为transient Node<K,V>[] table;的Node数组，从源码中看，我们的数组中每个Node节点不一定是链表结构的起始节点，而且可以是树结构的根节点。
在putVal()中我们注意到resize()方法，我们看看HashMap是怎样扩容(再散列)的：
final Node<K,V>[] resize() {
// 1. 初始化必要的变量
Node<K,V>[] oldTab = table; // 暂存旧容器
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧容量
int oldThr = threshold; // 旧阈值
int newCap, newThr = 0; // 初始化新的容量和阈值
// 2. 计算新阈值和新容量
if (oldCap > 0) { // 如果旧容量大于0
if (oldCap >= MAXIMUM_CAPACITY) { // 旧容量大于最大允许容量
threshold = Integer.MAX_VALUE; // 阈值设为最大
return oldTab; // 无法再扩容，直接返回旧容器
}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)// 否则新容量加倍
newThr = oldThr << 1; // 新容量没超过最大容量，阈值加倍
}else if (oldThr > 0)
newCap = oldThr; // 用旧阈值代替新容量
else { // 否则用默认值初始化新容量和新阈值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 上面分支计算完，如果新阈值为0
float ft = (float)newCap * loadFactor; // 计算阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 得到最终阈值更新
@SuppressWarnings({"rawtypes","unchecked"})
// 3. 再散列过程
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 根据新容量建一个新容器
table = newTab; // 用新容器替代原来的容器
if (oldTab != null) { // 如果旧容器非空
for (int j = 0; j < oldCap; ++j) { // 遍历旧容器的每一个桶位
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 该桶位赋值给e,如果非空
oldTab[j] = null;
if (e.next == null) //e.next为空，该桶位只有一个节点
newTab[e.hash & (newCap - 1)] = e; // 直接存给新桶
else if (e instanceof TreeNode) // 如果是树结构的根节点
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历桶中的链表
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 索引值不变
if (loTail == null)
loHead = e; // 头结点
else
loTail.next = e; // 连接新元素
loTail = e; // 尾结点指向下一位
}
else { // 索引值改变
if (hiTail == null)
hiHead = e; // 头结点
else
hiTail.next = e; // 连接新元素
hiTail = e; // 尾结点指向下一位
}
} while ((e = next) != null);
// 保存到(j)位置，即原位置
if (loTail != null) {
loTail.next = null; // 尾结点设为null
newTab[j] = loHead; // 数组前半段
}
// 保存到(oldCap + j)位置，即后半段
if (hiTail != null) {
hiTail.next = null; // 尾结点设为null
newTab[j + oldCap] = hiHead; // 数组后半段
}
}
}
}
}
return newTab;
}在计算新的索引值时，值的注意的是数组扩容后是之前的2倍(newCap = 2\(\times\)oldCap)，我们计算新位置时用的是e.hash &（newCap - 1)= e.hash &(2*\(\times\)oldCap -1)。以oldCap = 8,newCap = 16为例：
public V get(Object key) {
Node<K,V> e;
// 调用getNode
return (e = getNode(hash(key), key)) == null ? null : e.value;
}/**
* @param hash key的散列值
* @param key 键对象
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 在判断时 first = tab[(n - 1) & hash]已经根据计算找到对应的桶位
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // 检查第一个结点是要找的么
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode) // 是树节点就getTreeNode搜索并返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { // 是链表就继续向下搜索
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))//找到
return e;// 返回
} while ((e = e.next) != null);
}
}
return null; // 没找到返回null
}遍历方法我直接搜了个网址HashMap遍历的四种方法，列举方法比较详尽，这里我就不详细说了。
一般遍历都是采用遍历map.entrySet()，或者用map.entrySet().iterator()返回一个迭代器。差异在后者采用迭代器的方式能够通过Itertor中的remove()方法删除一个entry。另外还有两种只遍历map.keySet()和map.values()的方法。但是通过map.keySet()得到key在去调用map.get(key) 遍历values是效率底下的，不推荐使用。
接下来我们看看HashMap中的entrySet()方法：
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}该方法直接返回了一个内部类EntrySet的引用，查看该内部类并没有显示的定义任何构造函数，即调用的是默认的无参构造函数，所以该方法仅仅是返回了一个EntrySet引用。
观察EntrySet中继承了AbstractSet, AbstractSet又是继承自AbstractCollection, 查看AbstractCollection我们看到了public abstract Iterator<E> iterator();EntrySet中实现的itertor()来源就是这里，搞了半天迭代器是来源是这么追溯的EntrySet-->AbstractSet-->AbstractCollection-->Collection-->Iterable，Iterable中的iterator()是一切iterator的来源。
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}在遍历时，像这样：
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue())当我们调用增强for循环时，会自动调用map.entrySet()返回引用的类的iterator()方法,该方法又返回一个内部类的引用EntryIterator():
final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}该类继承了HashIterator实现了Iterator接口。在调用增强for循环时会调用hasNext()和next()方法，就来自这儿。
next()方法返回nextNode();，该方法是内部类HashIterator中的方法，它返回了容器中的下一个节点，方法如下：
// 下面current,next,expectedModeCount,index都是HashIterator在new EntryIterator()被子类初始化的。
public final boolean hasNext() {
return next != null;// next是下一个entry
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 先遍历链表next = (current = e).next，在遍历下一个桶位next = t[index++]链表
// 这里t=table直接获取外部类容器了,所以数据是这么获取到的
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}所以这里我们可以总结一下增强for循环遍历集合：编译器会自动执行集合的iterator()方法返回Iterator实例， 然后根据泛型声明一个指定对象类型的对象，然后进行while循环，使用Iterator的hasNext()方法和next()方法进行取值。
当然我们也可以这样遍历：
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());这样相当于直接显示调用的EntrySet的iterator()方法得到Iterator实例，然后进行显示的遍历。
equals()和hashCode()都是Object根类的方法，下面是Object根类中两个方法：
public boolean equals(Object obj) {
return (this == obj);
}
public native int hashCode();从上面代码，我们可以看出，equals()方法默认比较的是两个对象的地址，如果需要比较两个对象的内容需要我们自己去覆盖该方法。hashCode()则是一个native方法，它的具体实现不是由Java语言实现的，该方法返回的是一个与Object对象地址等信息相关的整数。
equals()方法设计是专门用来比较两个对象的，如果不覆盖原始的Object.equals()方法，则比较的是对象地址，这和==有点类似。如果我们需要定义自己的类，并实现内容的比较，则需要自己覆盖此方法。Java集合类中对equals()就是覆盖了的，另外在自定义对象基于比较(如排序)中也是需要覆盖此方法的。
那么如何写覆盖一个equals()方法呢？需要遵循下面的规则(摘自《Java编程思想》)：
如果要使用自己的类作为HashMap的键，必须重写equals()和hashCode()方法。事实上，所有与hash有关的集合类都是覆盖过Object.hashCode()方法的。
编写hashCode()我们需要明确，多个对象是可以有相同散列码的，但是无论何时同一个对象调用hashCode()都应该生成同样的值，并且好的hashCode()方法产生散列码应当尽量分布均匀。《Java编程思想》中引用了《Effective Java Programming Language Guide》一书中的指导：
| 域类型 | 计算 |
|---|---|
| boolean | c=(f?0:1) |
| byte,char,short,int | c=(int)f |
| long | c=(int)(f^(f>>>32)) |
| float | c=Float.floatToIntBits(f) |
| double | c=long l = Double.doubleToLongBits(f) |
| Object,其equals()调用这个域的equals() | c=f.hashCode() |
| 数组 | 对每个元素应用上述规则 |
终于写完了，估计内容会有一些地方不正确，希望读到的网友指出来，我好改过来，免得误导大家。
原文：https://www.cnblogs.com/snailvan/p/10671171.html