当前位置：首页 > article >正文

Java-数据结构-Map和Set-(二)-哈希表 |ू･ω･` )

article 2024/9/29 21:51:34

文本目录：

❄️一、哈希表：

☑ 1、概念：

☑ 2、冲突-概念：

☑ 3、冲突-避免：

☞ 1）、避免冲突-哈希函数的设计：

☞ 2）、避免冲突-负载因子调节(重点)：

☑ 4、冲突-解决：

➷ 1）、解决冲突-闭散列：

➷ 2）、解决冲突-开散列 / 哈希桶(重点)：

☑ 5、哈希表的实现：

▶ 1）、put(int key,int value)方法：

▶ 2）、getVal(int key)方法：

☑ 6、性能分析：

☑ 7、和Java类集的关系：

❄️总结：

❄️一、哈希表：

☑ 1、概念：

顺序结构以及平衡树中，元素存储码与其存储位置之间没有对应的关系，因此在我们查找一个元素的时候呢，必需要根据关键码的多次比较。

顺序查找的时间复杂度为O(N)，在平衡树中查找的话就是树的高度为O(logN)。搜索效率取决于搜索过程中元素的比较次数。

我们理想的搜索方法是：可以不经过任何的比较，一次直接从表中搜索到我们要查找的元素。如果构造一种数据结构，通过某种函数使元素的存储位置与它关键码之间能够建立一一映射关系，那么在查找中可以通过该函数快速查找到该函数。

实现：当向该结构中：

1、插入元素的时候：

可以根据待插入的关键码，以此函数计算出该元素的存储位置并按照此位置进行存放。

2、查找元素的时候：

对元素的关键码进行同样的函数计算，把得到的函数值。

该方法呢就是哈希(散列)方法，哈希方法的使用的转换函数称为哈希(散列)函数，其构造出来的结构称为哈希(散列)表。

我们来举一个例子来看看：数据为{1,7,6,4,9,5}；

哈希函数设置为：hash = key % capacity，其中capacity 是总空间的大小。

使用这个方法呢，进行搜索的时候呢，不需要进行多次关键字的比较，这直接可以找到，所以搜索效率比较高。但是还是有些问题的，我们如果插入 11 的话呢，11 % 10 = 1，但是 1 下标的位置呢，已经有元素了，这样呢就会产生所谓的 —— 冲突，那么我们要如何解决并且降低这种冲突呢？我们往后来看：

☑ 2、冲突-概念：

对于两个数据元素的关键字有 ki 和 kj (i != j)，有 ki != kj，但是呢 hash(ki) == hash(kj)，就是相当于 1 和 11 但是呢 hash(1) == hash(11)，在 capacity 为10 的情况下。

就是不同的关键字通过哈希函数计算相同的哈希地址，该种现象称为哈希冲突或者哈希碰撞。

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

☑ 3、冲突-避免：

我们呢要知道一个点，由于我们的哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致我们的冲突是必然要发生的，但是我们能做的就是尽量 降低冲突率。

☞ 1）、避免冲突-哈希函数的设计：

引起哈希冲突的可能的一个原因是：哈希函数设计不合理。

设计规则：

1、哈希函数的定义域必须包括存储的关键字码，而如果哈希表有 m 个地址，其值域必须在0-m-1之间。

2、哈希函数设计出来的地址能够均匀的分布在整个空间中。

3、哈希函数比较简单。

常见的哈希函数：

1、直接定制法(常用)：

取关键字的某个线性函数为散列地址：Hash(Key) = A * Key + B，优点：简单、均匀。

缺点：需要实现知道关键字的分布情况。使用场景：适合查找比较小并且连续的情况。

2、除留余数法(常用)：

设散列表中允许的地址数为 m，取一个不大于 m，但接近或者等于 m 的质数 p 作为除数。

按照哈希函数：Hash(Key) = key % p（p <= m），将关键码转换成哈希地址。

3、平方取中法(了解)：

这个用于不知道关键字的分布，而位数又不是很大的情况下。

比如：存放1234这个关键字，其平方为 1522756 ，抽取中间的三位数 227 作为哈希地址。

4、折叠法(了解)：

这个方法是关键字从左到右分割成位数相等的几个部分(最后一个部分可以短些)，然后将这几部分叠加求和，并按照散列表的表长，取后几位作为哈希地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5、随机取数法(了解)：

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key)，其中random 为随机数函数。
通常应用于关键字长度不等时。

6、数学分析法(了解)：

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

我们要注意：我们哈希函数设计的越好，其产生的哈希冲突呢就越小，但是呢还是无法解决冲突

☞ 2）、避免冲突-负载因子调节(重点)：

负载因子就是：填入表中的元素个数 / 散列表的长度 = 负载因子

我们的负载因子和填入表中的元素个数是成正比的，所以当我们的负载因子越大，可以填入的元素个数就越多，冲突发生的概率就越小，所以我们可以改变负载因子来调节冲突。

所以我们就可以提高散列表的长度来使复杂因子降低，就可以使填入的元素个数增加了。

我们的负载因子要控制在 0.7~0.8 之间。

我们了解了如何才能尽量避免冲突，接下来我们来看看如何才能解决冲突。

☑ 4、冲突-解决：

解决冲突的常见的两种方法就是：闭散列和开散列

➷ 1）、解决冲突-闭散列：

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去。

那么我们如何才能找到这个下一个位置呢？对于这个我们呢有两种方法可以找到：

1、线性探测：

就比如我们的上面的那个例子，如果我们想要插入 11 的话呢，就是根据哈希函数计算出我们的哈希地址之后呢我们查看这个地址是否有元素，如果有就放到其下一个位置，就可以了。

我们来看看这个例子：

缺点呢就是：这个方法呢会使冲突的元素集中到了一起。

我们的目的是把其芬分布的均匀一点，这个就有很大的缺陷。

2、二次探测：

我们的二次探测的方法呢，有一个公式可以找到要插入的位置：Hi = (H0 + i^2) % m 或者是 Hi = (H0 - i^2) % m ，其中呢 i = 1,2,3,4,5......... ，H0 是根据哈希函数计算出的 key 的哈希地址，m 呢是我们表的长度。

我们一上面的例子为例，来看看如何实现的：

但是呢对于闭散列呢有一个很大的缺陷，就是空间的利用率很低，这就是一个缺陷了，所以呢我们就有了两一种方法了——开散列/哈希桶。

➷ 2）、解决冲突-开散列 / 哈希桶(重点)：

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

其实就是数组+链表的一个组合方式。我们把每一个数据设为一个节点，放到我们的地址后面：

开散列可以看成是把每一个大集合中的搜索问题转化为小集合中的搜索问题。

☑ 5、哈希表的实现：

我们的 HashSet 的底层呢是 HashMap ，和我们上次介绍的 TreeSet 和 TreeMap 是差不多的，所以呢，这里我们自实现的哈希表呢就是 key-value 的，并且我们的哈希表是一个节点数组，所以我们来看看哈希表的的节点的代码，并且还要有我们的一个 负载因子：

public class HashBuck {
    //节点
    static class Node {
        public int key;
        public int value;
        public Node next;

        public Node(int key,int value) {
            this.key = key;
            this.value = value;
        }
    }
    //哈希桶是一个节点数组，所以我们使用节点来创建一个数组
    public Node[] array = new Node[10];
    //有效的数据长度
    public int usedSize;

    //负载因子
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;
}

▶ 1）、put(int key,int value)方法：

1、先使用哈希函数计算出 key 的哈希地址

2、我们检查一下我们的这个哈希地址下的数组中时候有 key 这个值。如果有就要更新 value。

3、如果没有和 key 相同的值，我们使用头插法进行把 key 值插入进去。(jdk1.8是尾插法)

4、usedSize++

5、我们的usedSize++，之后呢要检查我们的负载因子是否比我们的定义的大，如果大，我们就需要扩容。

对于这里的扩容方法呢，不是简单的直接把原数组扩大 2 倍就可以的，如果这样写就是不对的。

扩容的注意：

注意：就比如上面的例子，我们的扩大 2 倍之后呢，我们的长度是不是变成了 20，而我们的上面的 11 这个数据是不是就不是放到 1 这个地址的位置了，应该放到 11 这个位置了，所以我们的扩容方法呢，要遍历一遍我们的所有数据，对其进行重新计算哈希地址来放入我们的数据。

1、我们要把 cur.next 的位置记录下来，因为当我们把 11 放到新的位置之后呢，我们的cur这个的 next 节点就找不到了，所以我们需要记录下来。

来看看这个扩容的代码：

private void resize() {
        
        Node[] newarray = new Node[2 * array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int newindex = cur.key % newarray.length;
                Node curN = cur.next;
                cur.next = newarray[newindex];
                newarray[newindex] = cur;
                cur = curN;
            }
        }

        array = newarray;
    }

这样之后呢，我们来看看对于 put 这个方法是如何编写的：

public void put(int key,int value) {
        //计算地址
        int index = key % array.length;

        //检查是否出现相同的 key 值
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }

        //如果没有key值的话，使用头插法把新的节点插入到 哈希表中
        Node newNode = new Node(key,value);
        newNode.next = array[index];
        array[index] = newNode;

        //插入之后有效长度增加
        usedSize++;

        //判断负载因子
        if (loadFactor() >= DEFAULT_LOAD_FACTOR) {
            //扩容
            resize();
        }
    }

    //计算负载因子
    private double loadFactor() {
        return usedSize * 1.0 / array.length;
    }

▶ 2）、getVal(int key)方法：

对于这个呢就很简单了，我们同样先计算出我们的哈希地址之后呢，根据这个地址再来寻找我们传入的 key 所对应的 value 值。

我们呢来直接看代码如何编写的：

public int getVal(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }

        return -1;
    }

到这里我们的哈希表就结束了，对于哈希表就只实现这两个方法就可以了。

☑ 6、性能分析：

我们呢一般把每个桶中的链表的长度是一个常数，所以呢，通常我们的哈希表的插入/删除/查时间复杂度为 O(1)。

☑ 7、和Java类集的关系：

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
2. java 中使用的是哈希桶方式解决冲突的
3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

这个阈值是：数组长度大于 64 && 链表的长度超过了 8
4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。