【HashMap的底层数据结构——哈希表】_hashmap与哈希表

目录

引言

一、概念

二、哈希冲突

1.冲突-概念

2.冲突-避免（哈希函数设计）

3.冲突-避免及解决（重点掌握）

三、哈希表（桶）的实现

总结

引言

http://t.csdnimg.cn/z4XpR 在此篇博客中，介绍了Map集合实现类HashMap和TreeMap的使用，但并没有深究其底层的数据结构，下面介绍的就是HashMap和HashSet底层的数据结构——哈希表

一、概念

• 插入元素
  • 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素
  • 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若 关键码相等，则搜索成功

在Java 中，计算哈希值实际上是调用Object类中的hashCode()方法。

二、哈希冲突

1.冲突-概念

2.冲突-避免（哈希函数设计）

public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;
 
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
 
    private Node[] array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 10;//默认桶的大小
 
    public HashBucket() {
        array = new Node[DEFAULT_SIZE];
    }
 
    //添加键值对
    public int put(int key, int value) {
    }
 
    //重新哈希
    private void resize() {
    }
 
    //判断负载因子是否大于0.75
    private double loadFactor() {
        return size * 1.0 / array.length;
    }
 
    //获取键所对应的值
    public int get(int key) {
    }
}

• 重新哈希整体思路：

1. 对原哈希表二倍扩容得到新哈希表
2. 遍历原哈希表数组，对每个元素（链表）重新哈希。
3. 计算出重新哈希后的每个数组元素（桶）应插入位置。
4. 由于新数组各元素一定为空，直接将原哈希表元素（链表）放到新哈希表的应插入位置，尾插也可以。

完整代码如下：

//哈希表
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;
 
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
 
    private Node[] array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 10;//默认桶的大小
 
    public HashBucket() {
        array = new Node[DEFAULT_SIZE];
    }
 
    public int put(int key, int value) {
        //找到插入位置
        int index = key % array.length;
        Node node = new Node(key, value);
        //拿到该位置结点，遍历
        Node cur = array[index];
        //查看是否有相同键的结点
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return value;
            }
            cur = cur.next;
        }
        cur = array[index];
        //走到最后一个结点，尾插。
        while (cur != null && cur.next != null) {
            cur = cur.next;
        }
        if (cur != null) {
            cur.next = node;
        } else {
            array[index] = node;
        }
        size++;
        //判断负载因子是否超过0.75
        if (loadFactor() >= LOAD_FACTOR) {
            //重新哈希
            resize();
        }
        return -1;
    }
 
    //重新哈希
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        //遍历数组，对每个结点重新哈希
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int index = cur.key % newArray.length;
                //进行尾插
                Node node = newArray[index];
                while (node != null && node.next != null) {
                    node = node.next;
                }
                if (node != null) {
                    node.next = new Node(cur.key, cur.value);
                } else {
                    //如果直接赋cur，则cur的next也会带上
                    newArray[index] = new Node(cur.key, cur.value);
                }
                cur = cur.next;
            }
        }
        array = newArray;
    }
 
 
    private double loadFactor() {
        return size * 1.0 / array.length;
    }
 
    public int get(int key) {
        //1.找到位置  2.遍历
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }
}

总结

• 性能分析：

• 与Java类集的关系：

1. HashMap 和 HashSet 即 Java 中利用哈希表实现的 Map 和 Set。
2. Java 中使用的是哈希桶方式解决冲突的。
3. Java 会在链表长度大于一定阈值后（链表长度大于8，数组长度大于等于64），将链表转变为搜索树（红黑树）。
4. Java 中计算哈希值实际上是调用的 Object 类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。