目录介绍

  • 01.先来看一个问题
  • 02.官方解释散列表
  • 03.如何设计散列表
  • 04.哈希冲突怎么弄
  • 05.代码实现HashMap
  • 06.完整代码展示

01.先来看一个问题

  • 首先给大家抛一个问题，现有一个Person类包含name(假设姓名唯一)跟age的两个属性，要从1000个Person对象中找出name为“张三”的对象你该怎么做？
  • 第一种：有些同学要说话了：将1000个Person对象放入ArrayList中，再遍历ArrayList找出name为“张三”的对象不就得了。是的这种方法是可以的，但是假如张三恰好在最后一个那么就意味着要遍历1000次，这样效率就会非常低下。
  • 第二种：还有些同学说：将将1000个Person对象放入数组中，然后遍历找出name为“张三”的对象不就得。其实这个和第一种差不多。
  • 那么我们有没有什么办法来解决这种问题呢？别急学完散列表数据结构后答案自会揭晓。

02.官方解释散列表

  • 什么是散列表数据结构呢？来看一下它的官方解释:
    • 散列表（也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
  • 那些数据结构用到散列表
    • 就是通过键将一条记录保存到表中响应的位置，再通过键从表中取出记录。是不是有种似曾相识的感觉？没错Java中的HashTable和HashMap内部就是散列表数据结构。

03.如何设计散列表

  • 回到前面1000个Person的话题，假设如果我们用一个数组来存储Person对象，通过一个算法将Person中的name返回一个int类型值(这个算法也称之为hash算法)，我们就将这个int类型值最为数组的角标存储在数组中，获取的时候直接通过hash算法计算出数组角标然后直接获取到对应角标的元素，通过这种方式可以很大程度的提升查询效率。
  • 看似很完美，那么问题来了，如果通过hash算法得到的int值为10000那么是不是就意味着我至少要创建一个长度为10000的数组？看似是这样的，问题更严重，我还是老老实实用我的ArrayList吧~~~~首先我们可不可以这样做，我们将hash算法得到的值进行一个限制比如0-15，这样我们创建一个长度为16的数组就行了，那那那那问题又来了，假如张三和李四通过hash计算得到的值都是5而数组中一个角标只能存一个元素，怎么搞？？？其实这种情况就是我们经常听说的哈希冲突，怎么解决？别急，请看下一小节。

04.哈希冲突怎么弄

  • 解决哈希冲突的方法有很多，就选一种比较典型方式：链表法，所以不了解链表数据结构的同学可以先去熟悉一下。再回到Person的例子，假如张三和李四的hash值都是5那么我们可以将张三放在数组的第5个位置，李四以链表的形式放在张三后面，又来个王五hash值恰好也是5，那么我们就可以将王五放在李四的后面了，以此类推。详情如下图所示：
    • image
      image
  • 查询的时候首先计算出hash值得到角标，通过角标找到对应的链表头结点，然后再根据key值去链表中找具体的元素。

05.代码实现HashMap

  • 通过上面几个小节相信你已经熟悉了散列表的数据结构，下面我来带着大家通过代码实现一个简单的HashMap。实现步骤如下：
    • 设计节点类
    • 设计hash算法
    • 插入元素
    • 扩展数组
    • 查询元素

5.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;
    }
}

5.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)。

5.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;
}

5.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。注释写的很清楚就不过多赘述。

5.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;
}

06.完整代码展示

  • 代码如下所示
    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()、迭代器等等文章中就比一一讲解，感兴趣的同学可以自己实现。
贡献者: yangchong211