Java数据结构之散列表详解
介绍
本文详细介绍了散列表的概念、散列函数的选择、散列冲突的解决办法，并且最后提供了一种散列表的Java代码实现。
数组的特点是寻址容易，插入和删除困难；而链表的特点是寻址困难，插入和删除容易。而对于tree结构，它们的查找都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较，虽然查找和增删的综合效率较好，但是最终还是需要进行多次查找。为此引入了散列表来尝试进一步提升查找效率和增删的综合效率。
1 散列表概述
1.1 散列表概述
之前所掌握的查找算法，最简单的顺序表结构查找包括简单的顺序查找、二分查找、插值查找、斐波那契查找，以及后来的树结构查找包括二叉排序树、平衡二叉树、多路查找树、红黑树等。它们有一个功能特点就是，要查找的元素始终要与已经存在的元素进行多次比较，才能最终的出要该的元素是否存在或者不存在的结果。
我们知道，这些比较用于逐渐的定位某一个确切的位置，上面的大部分查找算法要求数据必须是有序存储的，算法就是通过比较两个数据的大小来缩小查找的范围，最终找到一个大小相等的数据，或说明该元素存在，或者最终也没有找到一个大小相等的数据，说明不存在。
为什么一定要“比较”？能否直接通过关键字key得到要查找的记录内存存储位置呢？当然有，这就是散列表。
事先在数据(这里可以是key-value键值对形式的数据，也可以是单个key形式的数据)的存储位置和它的关键字之间建立一个确定的对应函数关系f，使得每个关键字k对应一个存储位置f（key）。即：存储位置=f(key)，该映射被称为散列函数，利用散列函数来存储数据的数据结构被称为散列表。通过f(key)计算出存储位置的过程被称为散列，所得的存储位置称散列地址。
散列表通常基于数组来实现。存放数据的时候，散列函数f(key)根据key计算出数据应该存储的位置-数组下标，从而将不同的数据分散在不同的存储位置，这也是“散列”的由来；查找的时候，通过散列函数f(key)对应的key可以直接确定查找值所在位置-数组下标，而不需要一个个比较。这样就“预先知道”key所在的位置，直接找到数据，提升效率。散列表存放元素的数组位置也被称为“槽（slot）”。
散列表与线性表、树、图等结构不同的是，后几种结构数据元素之间都存在某种逻辑关系，而使用散列技术的散列表的数据元素之间不存在什么逻辑关系，元素的位置只与关键字key和散列函数f(key)有关联。
对于查找来说，散列技术简化了比较过程，效率就会大大提高，但万事有利就有弊，由于数据元素之间并没有确切的关系，散列技术不具备很多常规数据结构的能力。相对于其他查找结构，它只支持部分操作（查找、增删……），另一部分操作不能实现（排序、索引操作、范围查找、顺序输出、查找最大/小值……）。因此，散列表主要是面向查找的存储结构。
散列表的英文名称为 hash table，因此散列表又被称为哈希表，散列函数又被称为哈希函数，函数的实现步骤被称为散列算法/哈希算法。
1.2 散列冲突（hash collision）
我们还能看出来，散列算法实际上是将任意长度的key变换成固定范围长度的值。这种转换是一种压缩映射，简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。也就是，散列值的范围大小通常远小于输入的key的范围。
例如，输入的key为5,28,19,15,20,33,12,17,10，共9个，此时肯定不能将哈希表（内部数组）的长度初始化为33，那样的话就太浪费空间了。理想的结果是，将这9个key通过某个散列函数f(key)将它们放入长度为10的哈希表（数组）中，并且然而由于散列算法是一种压缩映射算法，散列表的长度单元是有限的，关键字key是无限的，对于某个散列算法，如果key样本如果大，那么两个不同的key映射到相同的单元，即f(key)的值相等的情况几乎是一种必然，这种现象也被称为散列冲突/哈希冲突。
例如对上面的key个数采用的散列函数是f(key)=key mod 9，f(5)=5，所以数据5应该放在散列表的第5个槽里；f(28)=1，所以数据28应该放在散列表的第1个槽里；f(19)=1，也就是说，数据19也应该放在散列表表的第1个槽里——于是就造成了碰撞。
尽管我们可以通过精心设计的散列函数让冲突尽可能的少，但是不能完全避免。因此散列表必须具备处理散列冲突的能力。
2 散列函数的选择
2.1 散列函数的要求
从上面的散列表的概述可以看出来，要实现散列表，最关键的就是散列函数f(key)的选择和处理散列冲突的能力，我们先来看散列函数的选择。
良好的散列函数应该满足下面两个原则：
- 计算简单：如果散列算法需要很复杂的计算，会耗费很多时间，这对于需要频繁地查找来说，就会大大降低查找的效率了。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
- 散列地址分布均匀：我们刚才也提到冲突带来的问题，虽然不能完全避免冲突，但是可能设计好的散列函数尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少冲突的发生和为处理冲突而耗费的时间。 下面介绍几种常用的散列函数构造方法！
2.2 散列函数构造方法
直接定址法
取关键字或关键字的某个线性函数值为散列地址（这种散列函数也叫自身函数）。f(key)=a×key+b（a、b为常数）。
比如对0-100岁人口数统计，直接采用年龄作为关键字。
比如统计1980年忠厚每年出生的人口数目，我们可以对出生年份关键字减去1980来作为地址。
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。
数字分析法
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
比如对于手机号码的key，用手机号码后四位参与计算。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。
折叠法
将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。 比如我们的关键字是9876543210，散列表表长为三位，我们将它分为四组，987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
平方取中法
取关键字平方后的中间几位为哈希地址。通过平方扩大差别，另外中间几位与乘数的每一位相关，由此产生的散列地址较为均匀。
假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用做散列地址。
平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。
除留余数法
此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：f(key)=key mod p(p≤m)
mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。很显然，本方法的关键就在于选择合适的p，p如果选得不好，就可能会容易产生冲突。HashMap就采用了这种方法（利用位运算代替取模运算，提高程序的计算效率）。需要注意的是，只有在特定情况下，位运算才可以转换成取模运算（当 b = 2^n 时，a % b = a & (b - 1) ）。
因此根据前辈们的经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。
随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址。也就是：f(key)=random(key)
这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考：
1.计算散列地址所需的时间。
2.关键字的长度。
3.散列表的大小。
4.关键字的分布情况。
5.记录查找的频率。
综合这些因素，才能决策选择哪种散列函数更合适。
3 散列冲突的解决
设计得再好的散列函数也不可能完全避免冲突。对无论以何种散列函数构建的散列表，还必须考虑如何处理散列冲突。常见方法有以下几种：
- 使用辅助数据结构：分离链接法/链地址法/拉链法
- 不使用辅助数据结构：开放定址法（线性探测、平方探测、双散列）
- 再散列
3.1 分离链接法
在存储数据的过程中，如果发生冲突，可以利用单链表在已有数据的后面插入新数据，访问的数组下标元素作为链表的头部。这种解决冲突的方法被称为“分离链接法”，又被称为分离链接法、拉链法。可以想象，除了链表之外，其他辅助结构都能解决冲突现象：二叉树或者另一张散列表，如果采用链表来辅助解决散列冲突，并且散列函数设计的很好，那么链表应该是比较短的，此时其他复杂的辅助结构便不值得尝试了。
如下图，使用链地址法的散列表：
JDK1.8之前的HashMap就是使用的链表来处理散列冲突，为了降低链表过长造成的遍历性能损耗，在JDK1.8中采用链表+红黑树的方法来处理散列冲突，当链表长度大于8个时，转换为红黑树，红黑树的查找效率明显高于单链表的。而小于等于8个时，采用链表则完全可以接受，避免红黑树的复杂结构。
3.2 开放定址法
开放定址法的基本思路就是出现冲突时，通过另外的算法寻找其他空余的位置，因此不需要额外的辅助数据结构，只要散列表足够大，空的散列地址总能找到，并将记录存入。
开放定址法法又可以分为线性探测法、平方探测法、双散列法。
3.2.1 线性探测法(Linear Probing)
线性探测公式为：（H（key）+di）％ m；其中H（key）为哈希函数，m 为表长-1，di为一个增量序列（di=0,1,2,3...,m-1）。
线性探测法的主要思想是：当发生碰撞时（一个键被散列到一个已经有键值对的数组位置），我们会检查数组的下一个位置，这个过程被称作线性探测。线性探测可能会产生三种结果：
- 命中：该位置的键与要查找的键相同；
- 未命中：该位置为空；
- 该位置的键和被查找的键不同。
当我们查找某个键时，首先通过散列函数得到一个数组索引后，之后我们就开始检查相应位置的键是否与给定键相同，若不同则继续查找（若到数组末尾也没找到就折回数组开头），直到找到该键或遇到一个空位置。由线性探测的过程我们可以知道，若数组已满的时候我们再向其中插入新键，会陷入无限循环之中。
3.2.2 平方探测法
如果散列函数选的不是那么的好，可能导致冲突不断出现。如果先存入key1，能够找到某个空余位置存入，存入key2时与key1冲突，此时被存入到key1的下一个位置，后来key3又与它们发生散列冲突……这样就出现了关键字聚集在某一区域的情况，即出现了数据聚集的现象。
一种解决方法是，增大di的增量：（H（key）+di²）％ m（di=0,1,2,3...,m/2）
增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为平方探测法。
如果m—表长-1不为素数，那么备选单元的数量将会减少，造成散列冲突的可能性就会大大增加。
3.2.3 双散列法
准备两个散列函数。双散列一般公式为：F(i)= i * hash2(x)，意思是用第二个散列函数算出x的散列值，然后在距离hash2(x)，2hash2(x)的地方探测。
3.3 再散列法
前面的链地址法和开放定址法都是为了让散列表中的元素分布的更加合理，但是散列表空间总有用完的时候，甚至当它们的散列表填充元素过多时，都会增大发生散列冲突的概率。这里的再散列法就是计算出什么时候让散列表进行扩展以及在散列表扩展的时候，如何让原来的元素在新的空间中合理的分布。
一般方法是：当散列表的元素足够的多时，建立另外一个大约两倍大的表，再用一个新的散列函数，扫描整个原始表然后按照新的映射插入到新的表里，这就是再散列。其开销非常大，因为涉及到所有元素的移动。
再散列的触发条件通常有：只要表有一半满了就做、只有当插入失败时才做（这种比较极端）、当表到达某个扩容因子时再做。第三种是较好的方法，HashMap就是用的这种方法。
散列表的扩容因子： 所谓的扩容因子α=填入表中的记录个数/散列表长度，α标志着散列表的装满的程度。一般来说，当元素数量达到设定的扩容因子的数量时，就表示可以进行再散列扩容了，也叫装填因子。因此一个合理的扩容因子非常重要。α越大，产生冲突的可能性就越大；α越小，产生冲突的可能性就越小，但是造成了空间浪费。JDK1.8的HasmMap装填因子默认为0.75。
4 散列表的简单实现
JDK已经提供了现成的散列表实现，比如著名的HashMap。JDK1.8的HashMap是采用数组+链表+红黑树来实现的。散列函数采用基于hashcode()的去除留余法，并且采用分离链接法和再散列法的散列冲突解决办法。
这里提供另一种采用线性探测的散列表的Java简单实现，从下面的实现上可以看出来，实际上线性探测的散列表效率并不高，并且产生了数据聚集，但是JDK中也有使用线性探测实现的散列表类，比如ThreadLocal中的ThreadLocalMap，因为线性探测的实现比较简单。
public class LinearProbingHashMap<K, V> {
transient Entry<K, V>[] table;
private static class Entry<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
private Entry(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
@Override
public final K getKey() {
return key;
}
@Override
public final V getValue() {
return value;
}
@Override
public final String toString() {
return key + "=" + value;
}
@Override
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
@Override
public int hashCode() {
return hash;
}
}
private int capacity = 16;
private int size;
public LinearProbingHashMap() {
}
public V put(K key, V value) {
//初始化
if (table == null) {
table = new Entry[capacity];
}
//扩容,这里判断元素数量大于等于0.75*capacity
if (size >= capacity * 0.75) {
resize(2 * capacity);
}
int hash = hash(key);
//计算应该插入的数组元素下标
int position = hash & (capacity - 1);
//插入逻辑,总会成功
while (true) {
if (table[position] == null) {
table[position] = new Entry<>(hash, key, value);
size++;
break;
//判断是否是重复的key,这里使用hash值和==判断
} else if (hash == table[position].hashCode() && table[position].getKey() == key) {
return table[position].setValue(value);
}
position = nextIndex(position, capacity);
}
return null;
}
public V get(K key) {
if (table == null) {
return null;
}
//计算出key对应的数组位置
int position = hash(key) & (capacity - 1);
//如果该位置不为null,则开始查找连续的元素
if (table[position] != null) {
do {
if (table[position].getKey() == key) {
return table[position].getValue();
}
position = nextIndex(position, capacity);
} while (table[position] != null);
}
return null;
}
public V delete(K key) {
if (table == null) {
return null;
}
//计算出key对应的数组位置
int position = hash(key) & (capacity - 1);
V value;
//如果该位置不为null,则开始查找连续的元素
if (table[position] != null) {
do {
if (table[position].getKey() == key) {
//删除元素
value = table[position].getValue();
table[position] = null;
size--;
//将后面的连续的元素全部重新插入
position = nextIndex(position, capacity);
Entry<K, V> positionEntry;
while ((positionEntry = table[position]) != null) {
table[position] = null;
size--;
put(positionEntry.getKey(), positionEntry.getValue());
position = nextIndex(position, capacity);
}
return value;
}
position = nextIndex(position, capacity);
} while (table[position] != null);
}
return null;
}
public int size() {
return size;
}
private int hash(K key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
private void resize(int newCapacity) {
if (newCapacity <= 0) {
throw new StackOverflowError("容量超出最大容量");
}
this.capacity = newCapacity;
Entry<K, V>[] oldTab = table;
table = new Entry[capacity];
for (Entry<K, V> e : oldTab) {
if (e != null) {
int position = e.hashCode() & (capacity - 1);
while (table[position] != null) {
position = nextIndex(position, capacity);
}
table[position] = e;
}
}
}
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}
@Override
public String toString() {
return "LinearProbingHashST{" +
"table=" + Arrays.toString(table) +
'}';
}
}4.1 测试
public class LinearProbingHashMapTest {
public static void main(String[] args) {
System.out.println("==========>插入一批元素");
LinearProbingHashMap<Object, Object> objectObjectLinearProbingHashMap = new LinearProbingHashMap<>();
objectObjectLinearProbingHashMap.put(49, 16);
objectObjectLinearProbingHashMap.put("Aa", 1);
objectObjectLinearProbingHashMap.put(34, 78);
objectObjectLinearProbingHashMap.put(17, 85);
//Aa与BB的hash值是一样的
objectObjectLinearProbingHashMap.put("BB", 2);
objectObjectLinearProbingHashMap.put(36, 36);
objectObjectLinearProbingHashMap.put(21, 37);
objectObjectLinearProbingHashMap.put(9, 87);
objectObjectLinearProbingHashMap.put("兓", 62);
objectObjectLinearProbingHashMap.put(46, 43);
objectObjectLinearProbingHashMap.put("呵呵", 3);
objectObjectLinearProbingHashMap.put("嘻嘻", 4);
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>删除 BB");
Object delete = objectObjectLinearProbingHashMap.delete("BB");
System.out.println(delete);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>插入(46,44) 重复添加46,将会替换value");
Object put = objectObjectLinearProbingHashMap.put(46, 44);
System.out.println(put);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>插入null 将会尝试添加到第一个元素");
Object putNull = objectObjectLinearProbingHashMap.put(null, "nullnull");
System.out.println(putNull);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>获取null 对应的value");
Object o = objectObjectLinearProbingHashMap.get(null);
System.out.println(o);
System.out.println("==========>扩容");
objectObjectLinearProbingHashMap.put("BB", 5);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>获取BB 对应的value");
Object bb = objectObjectLinearProbingHashMap.get("BB");
System.out.println(bb);
System.out.println("==========>删除 34");
Object delete34 = objectObjectLinearProbingHashMap.delete(34);
System.out.println(delete34);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
}
}
以上就是Java数据结构之散列表详解的详细内容，更多关于Java 散列表的资料请关注编程网其它相关文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
