前言
首先给大家抛一个问题，现有一个Person类包含name(假设姓名唯一)跟age的两个属性，要从1000个Person对象中找出name为“张三”的对象你该怎么做？有些同学要说话了：将1000个Person对象放入ArrayList中，再遍历ArrayList找出name为“张三”的对象不就得了。是的这种方法是可以的，但是假如张三恰好在最后一个那么就意味着要遍历1000次，这样效率就会非常低下，那么我们有没有什么办法来解决这种问题呢？别急学完散列表数据结构后答案自会揭晓。
1. 概述
什么事散列表数据结构呢？来看一下它的官方解释:
散列表（也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
什么乱七八糟的，越看越晕~~~其实就是通过键将一条记录保存到表中响应的位置，再通过键从表中取出记录。是不是有种似曾相识的感觉？没错Java中的HashTable和HashMap内部就是散列表数据结构。
2. 散列表设计
回到前面1000个Person的话题，假设如果我们用一个数组来存储Person对象，通过一个算法将Person中的name返回一个int类型值(这个算法也称之为hash算法)，我们就将这个int类型值最为数组的角标存储在数组中，获取的时候直接通过hash算法计算出数组角标然后直接获取到对应角标的元素，通过这种方式可以很大程度的提升查询效率。
嗯，看似很完美，那么问题来了，如果通过hash算法得到的int值为10000那么是不是就意味着我至少要创建一个长度为10000的数组？看似是这样的，问题更严重，我还是老老实实用我的ArrayList吧~~~~哈哈哈，有问题就要解决啊，要不然我写着文章还有mao用。。。首先我们可不可以这样做，我们将hash算法得到的值进行一个限制比如0-15，这样我们创建一个长度为16的数组就行了，那那那那问题又来了，假如张三和李四通过hash计算得到的值都是5而数组中一个角标只能存一个元素，怎么搞？？？其实这种情况就是我们经常听说的哈希冲突，怎么解决？别急，请看下一小节。
3. 哈希冲突
解决哈希冲突的方法有很多，本篇文章就选一种比较典型方式：链表法，所以不了解链表数据结构的同学可以先去熟悉一下。再回到Person的例子，假如张三和李四的hash值都是5那么我们可以将张三放在数组的第5个位置，李四以链表的形式放在张三后面，又来个王五hash值恰好也是5，那么我们就可以将王五放在李四的后面了，以此类推。详情如下图所示：
hash.png
查询的时候首先计算出hash值得到角标，通过角标找到对应的链表头结点，然后再根据key值去链表中找具体的元素。
4. 代码实现
通过上面几个小节相信你已经熟悉了散列表的数据结构，下面我来带着大家通过代码实现一个简单的HashMap。实现步骤如下：
- 设计节点类
- 设计hash算法
- 插入元素
- 扩展数组
- 查询元素
4.1 设计节点类
本例中解决哈希冲突采用单向链表，代码如下：
//节点对象
public class Node<K,V>{
K key;//键
V value;//值
Node<K,V> next;//下一个节点对象
public Node(K key,V value,Node<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
节点的键值为泛型类型，包含三个属性：键、值、后继节点，没啥难的就不多做解释。
4.2 hash算法
前面我提到过hash算法有很多种，本篇文章侧重点为散列表数据结构，所以我就设计了一个较为简单的hash算法(难的我也写不出来啊~~~)，代码如下：
//传入key值
public int hash(K key){
//获取到key的hashCode值
int code = key.hashCode();
//defaultCapacity为数组长度，默认为16
return code%(defaultCapacity-1);
}
是有点简单，加上大括号才四行代码。。。。defaultCapacity为当前数组的长度，所以该hash算法的值被限制在了0-(defaultCapacity-1)。
4.3 插入元素
插入元素需要考虑的因素比较多，我个人把它细分为4步
步骤：
- 计算key的哈希值，即存储角标
- 判断key值是否已经存在(散列表中不允许重复key)，如果存在就将value替换
- 判断是否需要扩容(下一小节会讲到)
- 将key、value生成节点对象以头结点的形式存入到数组中
代码：
//添加元素
public V put(K key,V value){
//初始化数组
if(nodes==null){
nodes = new Node[defaultCapacity];
}
int index = hash(key);//计算存储角标
//获取到数组角标元素，可视为头结点
Node<K,V> node = nodes[index];
//遍历链表中节点对象
while (node!=null){
//存在重复key将value替换
if(node.key.equals(key)){
node.value = value;
return value;
}else {
node = node.next;
}
}
//判断是否需要扩展defaultCapacity为数组长度，
//defaultLoadFactor为扩展因子默认0.75
if(size>=defaultCapacity*defaultLoadFactor){
resize();
}
//将新添加的数据作为头结点添加到数组中
nodes[index] = new Node<>(key,value,nodes[index]);
size++;
return value;
}
4.4 扩展数组
关于数组扩容这一块我详细说一下，如果defaultCapacity的值始终是16，那么当数据量较大的情况下数组中的链表会很长，虽然通过hash算法可以得到角标中头结点，但仍要花大量时间去链表中查找元素，所以要在相应的时机对数组进行扩容，扩容后对所有数据重新再散列。一般来说通过定义的扩展因子来决定是否扩容，假如扩展因子为0.75，那么当散列表中元素达到defaultCapacity*0.75时需进行扩容操作。具体代码如下：
//扩展数组
public void resize(){
//扩容后要对元素重新put(重新散列)，所以要将size置为0
size=0;
//记录先之前的数组
Node<K,V>[] oldNodes = nodes;
defaultCapacity = defaultCapacity*2;
nodes = new Node[defaultCapacity];
//遍历散列表中每个元素
for (int i = 0;i<oldNodes.length;i++){
//扩容后hash值会改变，所以要重新散列
Node<K,V> node = oldNodes[i];
while (node!=null){
Node<K,V> oldNode = node;
put(node.key,node.value);//散列
node = node.next;//角标往后移
oldNode.next = null;//将当前散列的节点next置为null
}
}
}
重新散列后一定要将当前节点的next置为null。注释写的很清楚就不过多赘述。
4.5 查询元素
查询元素就比较简单了，首先通过hash算法计算出角标位置，然后获取头结点再对链表进行遍历，如果存在符合的key就将value返回，代码如下：
//获取元素
public V get(K key){
//获取角标位置
int index = hash(key);
//获取头结点
Node<K,V> node = nodes[index];
if(node!=null){
//遍历链表
while (node!=null&&!node.key.equals(key)){
node = node.next;
}
if(node==null){
return null;
}else {
return node.value;
}
}
return null;
}
4.6 完整代码
public class ZsHashMap<K,V> {
private Node<K,V>[] nodes;//存储头节点的数组
private int size;//元素个数
private static int defaultCapacity = 16;//默认容量
private static float defaultLoadFactor = 0.75f;//扩展因子
public ZsHashMap(){}
public ZsHashMap(int capacity,int loadFactor){
defaultCapacity = capacity;
defaultLoadFactor = loadFactor;
}
//添加元素
public V put(K key,V value){
//初始化数组
if(nodes==null){
nodes = new Node[defaultCapacity];
}
int index = hash(key);//计算存储角标
//获取到数组角标元素，可视为头结点
Node<K,V> node = nodes[index];
//遍历链表中节点对象
while (node!=null){
//存在重复key将value替换
if(node.key.equals(key)){
node.value = value;
return value;
}else {
node = node.next;
}
}
//判断是否需要扩展defaultCapacity为数组长度，
//defaultLoadFactor为扩展因子默认0.74
if(size>=defaultCapacity*defaultLoadFactor){
resize();
}
//将新添加的数据作为头结点添加到数组中
nodes[index] = new Node<>(key,value,nodes[index]);
size++;
return value;
}
//获取元素
public V get(K key){
//获取角标位置
int index = hash(key);
//获取头结点
Node<K,V> node = nodes[index];
if(node!=null){
//遍历链表
while (node!=null&&!node.key.equals(key)){
node = node.next;
}
if(node==null){
return null;
}else {
return node.value;
}
}
return null;
}
//扩展数组
public void resize(){
//扩容后要对元素重新put(重新散列)，所以要将size置为0
size=0;
//记录先之前的数组
Node<K,V>[] oldNodes = nodes;
defaultCapacity = defaultCapacity*2;
nodes = new Node[defaultCapacity];
//遍历散列表中每个元素
for (int i = 0;i<oldNodes.length;i++){
//扩容后hash值会改变，所以要重新散列
Node<K,V> node = oldNodes[i];
while (node!=null){
Node<K,V> oldNode = node;
put(node.key,node.value);//重新散列
node = node.next;//指针往后移
oldNode.next = null;//将当前散列的节点next置为null
}
}
}
//hash算法
public int hash(K key){
int code = key.hashCode();
return code%(defaultCapacity-1);
}
//节点对象
public class Node<K,V>{
K key;
V value;
Node<K,V> next;
public Node(K key,V value,Node<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
}
来做一下测试：
ZsHashMap<String,Integer> map = new ZsHashMap<>();
map.put("a",1);
map.put("b",2);
map.put("b",3);
System.out.println(map.get("a"));
System.out.println(map.get("b"));
打印结果：
1
3
我刻意的将b添加两次，从打印结果来看第二次对第一次进行了覆盖。到这一个简单的散列表就实现了，其实还可以加入很多扩展的方法， 比如remove()、迭代器等等文章中就比一一讲解，感兴趣的同学可以自己实现。
总结
我一直都认为，一个合格的Coder要保持一种精神：“知其然更要知其所以然”，比如今天的散列表，如果你不清楚它的内部原理你是不会明白它的优点是什么，更别说去灵活的运用，当然学习数据结构好处远不止此。本篇文章内容差不多就这些了，以后我还会陆续推出数据结构的文章，希望大家继续关注。
网友评论