[Java数据结构与算法] 哈希表（Hash Table）

[Java数据结构与算法] 哈希表（Hash Table）

一、概念与原理

在顺序结构和平衡树中，元素关键码和其存储位置没有对应关系。

这导致查找元素时，需要进行多次关键码之间的比较java hashcode原理，搜索的效率取决于搜索过程中的比较次数。

有没有一种方法，能够避免对关键码进行比较，以此提高效率呢？

我们期望：不经过任何比较，直接从表中获取到要搜索的元素。

哈希表（散列表）是一种通过哈希函数（散列函数）进行元素的增删查改操作构造出来的数据结构。

这种方法称为哈希（散列）方法。

例如，数据｛12，5，3，8，0，6｝

哈希函数设置为：Hash(key) = key % ，是存储元素的底层的总空间大小（如数组）

= 10

Hash(12) = 12 % 10 = 2，即元素12要放到下标为2的位置

其余元素也是一样：

Hash(5) = 5 % 10 = 5，Hash(3) = 3 % 10 = 3，Hash(8) = 8 % 10 = 8，Hash(0) = 0 % 10 = 0，Hash(6) = 6 % 10 = 6。

使用哈希方法进行搜索不用多次进行关键码的比较，直接取得存储位置，因此效率较快。

在我们使用 时，新建的哈希表的默认长度是 1 * 2⁴ = 16。

但是，当两个元素通过哈希函数计算得到的结果是相同的，那该怎么办呢？

二、哈希冲突

不同的关键字通过相同的哈希函数得到相同的哈希地址，此现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

避免哈希冲突

由于哈希表底层的空间大小往往是小于所要存储的数据的容量大小的，因此java hashcode原理，哈希冲突的发生是必然的。我们要做的是降低冲突率。

1. 哈希函数设计原则

常见哈希函数：

一般来说，我们不需要上手设计哈希函数，使用时直接用Java内置的原生哈希函数即可。

2. 调节负载因子（重点）

散列表的荷载因子定义：α = 填入散列表的元素个数 / 散列表的长度

解决哈希冲突

1. 闭散列（开放地址法）

当发生哈希冲突时，若哈希表未被装满，说明表中还有空位，此时就可以把元素存放空位中去。

寻找空位的方式有两种：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置[Java数据结构与算法] 哈希表（Hash Table），就不会存在表满的问题。

在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

2. 开散列 / 哈希桶（链地址法）（重点）

首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

哈希桶的实现

public class MyHashBuck {
    public static class Node {
        public K key;
        public V val;
        public Node next;
        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] arr;
    public int usedSize;
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;
    public void push (K key, V val) {
        // 先查找链表中是否有该key，若有，就更新val
        // 引用类型先获取哈希码再哈希求位置
        int hashCode = key.hashCode();
        int index = hashCode % arr.length;
        Node cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        // 当前链表中没有该key，插入结点(头插法)
        Node node = new Node(key,val);
        node.next = arr[index];
        arr[index] = node;
        usedSize++;
    }
    public V getVal (K key) {
        int hashCode = key.hashCode();
        int index = hashCode % arr.length;
        Node cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}

性能分析

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的。

因此，哈希表的插入/删除/查找时间复杂度是O(1) 。

冲突严重时的解决方法

使用哈希桶能够有效解决数据存放的冲突问题[Java数据结构与算法] 哈希表（Hash Table），但是如果冲突严重，估计小集合的效率也会不尽人意，此时可以对小集合进行转化，如每一个桶的底层是一个哈希表 / 搜索树。

三、和Java类集的关系1. 和 就是 Java 中以哈希表为底层结构实现的 Map 和 Set2. Java 中使用的是 哈希桶 方式解决冲突的

长度通常都是2的幂次。

3. Java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

树化的条件：

当两个条件都达到要求，才会转变为红黑树。

解树化的条件：节点个数达到6个

即当节点个数为6个时，就把红黑树转成链表。

4. Java 中计算哈希值实际上是调用的类的 方法

进行 key 的相等性比较时调用 key 的 方法。

所以如果要用自定义类作为 的 key 或者 的值java hashcode原理，必须覆写 和 方法，而且要做到 相等的对象， 一定是一致的。