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

[入门JAVA数据结构 JAVADS] 哈希表的初步介绍和代码实现

news 来源：原创 2025/5/22 11:32:17

前言

哈希表的概念和诞生的原因

哈希冲突

简单实现哈希表

基本属性

插入

获取key的val

计算负载因子

扩容(难点)

完整代码(方便大家复制自己去调试)

数据是int的

使用泛型实现的

结尾

前言

笔者鸽了接近两个月后决定"勤政"了.尽力把学过的知识写下来.为了我自己,也为了我的读者.

本博客展示代码均在本人的Github 有备份,地址为 MyJava/JavaDS2 at main · calljsh/MyJava

如果您觉得对您有启发和帮助,还请给个赞或者收藏,谢谢您

哈希表的概念和诞生的原因

我们如果正常想要去一组数据集合中找某一个数据,时间复杂度必然都不是O(1), 因为我们要进行多次的比较搜索的效率取决于搜索过程中元素的比较次数。所以我们需要一个理想的方法,让搜索的过程一次就好!

如果构造一种存储结构，通过某种函 数 使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快 找到该元素 。哈希表就这么产生了!

哈希表（Hash Table）是一种数据结构，用于通过计算元素的哈希值来高效地存储和查找数据。它是基于数组实现的，并且通过哈希函数将元素映射到数组中的一个位置（即桶或槽），从而实现快速查找、插入和删除操作。

通俗来说就是一个查字典的过程, 我们可以通过查读音或者查部首来存储和确定汉字的位置,字典就是哈希表,查读音或者查部首就是哈希函数,汉字就是我们的数据

通过查阅资料可知,哈希表的基本组成大概有这么几个部分

哈希函数（Hash Function）
哈希函数是哈希表的核心，负责将输入的键（Key）映射到表中的一个索引位置。理想的哈希函数能够均匀地分配键值，尽量减少碰撞。常见的哈希函数有除法法（通过键对一个素数取余）和乘法法（通过键与常数相乘后取余）等。
桶（Bucket）或槽（Slot）
哈希表内部通常使用一个数组来存储元素，每个数组元素被称为一个“桶”或“槽”。每个桶可以存放多个键值对，通常通过哈希函数计算得出的位置来决定数据放置在哪个桶中。桶的数量通常是哈希表的大小。
碰撞处理机制(哈希冲突)（Collision Resolution）
当两个不同的键通过哈希函数计算得出相同的索引位置时，称为碰撞(哈希冲突)。为了解决碰撞问题，哈希表采用不同的碰撞处理策略，常见的有：
- 链式地址法（Chaining）：每个桶存储一个链表（或其他数据结构），当发生碰撞时，将元素追加到该链表中。
- 开放地址法（Open Addressing）：如果发生碰撞，哈希表会按照一定的探测方式（如线性探测、二次探测或双重哈希）查找下一个空桶存放元素。
负载因子（Load Factor）
负载因子是哈希表中元素数量与桶的数量之间的比值。负载因子过高会导致频繁碰撞，从而降低性能。因此，哈希表通常会在负载因子超过某个阈值时进行扩容，增加桶的数量，以保持操作的效率。
扩容（Rehashing）
当哈希表的负载因子超过一定阈值时，哈希表会进行扩容。扩容通常是通过创建一个更大的数组，并重新计算所有元素的哈希值，重新分配到新的桶中。扩容通常是一个时间复杂度较高的操作，因此需要合理设置负载因子来平衡空间与时间效率。

举个例子例如：数据集合{1，7，6，4，5，9}；

我们设置一个哈希函数 hash(key) = key %cap , 假设我们的 cap = 10; 那么每个数据位置应该如下图所示

哈希冲突

从举例来看,如果我再添加几个数据,例如14,15,16,17这不炸了吗?数组上已经有了数据了,这几个数据我们应该放到哪里去? 没错,这就是哈希冲突

对于两个数据元素的关键字和 (i != j) ，有 != ，但有： Hash( ) == Hash( ) ，即： 不同关键字通过相同哈 希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞 。

常见的的缓解这一现象的方法上面已经举例过了,但尽管如此,资料表明,哈希冲突是不可避免的,我们只能通过更精细的设计去降低它带来的负面效果.

已经在理论上说了很多了,我们重点还是移动到我们的代码上,接下来,笔者自己通过" 链式地址法"去实现一个简单的哈希表.

简单实现哈希表

首先我们要明确一点,我们在这里实现的哈希表是一个"链表数组",也就是说,数组的每个索引都是一个链表

链式地址法（Chaining）：每个桶存储一个链表（或其他数据结构），当发生碰撞时，将元素追加到该链表中。

如图所示

基本属性

首先我们要构建好结点,每个结点都需要有key 和 value, 还需要地址域,作为一个内部类.

    static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}

然后创建 Node数组,写好我们的负载因子,选择0.75是因为JAVA系统库限制的负载因子为0.75

    public Node[] arr;public int usedsize;public  static final   float  loadnum = 0.75f;public Hashmap() {this.arr = new Node[10];  // 初始化数组容量为 10}

插入

插入方法的思路比较明确和简单,首先根据我们的哈希函数确定数据应该放的位置a,然后看看位置a是否已经有了其他的数据,如果有,就通过尾插法插入到链表的最后去(相同的key就对val进行替换),最后计算负载因子,如果超过0.75就进行扩容. 代码如下

  public void put(int key, int val) {int idx = key % arr.length;Node cur = arr[idx];// 如果链表已经存在，检查是否有相同 keywhile (cur != null) {if (cur.key == key) {cur.val = val;  // 更新值return;}cur = cur.next;}// 插入新节点（尾插法）Node newNode = new Node(key, val);// 如果当前桶为空，直接插入if (arr[idx] == null) {arr[idx] = newNode;} else {// 否则，找到链表的尾部插入新节点Node cur2 = arr[idx];while (cur2.next != null) {cur2 = cur2.next;}cur2.next = newNode;}usedsize++;if(loadnum()>loadnum){resize();}}

获取key的val

为了更方便地获取某个key的值也是我们创建哈希表的初衷,具体的思路就是查找它的哈希地址,然后遍历该索引的链表,去查找是否有对应key的val. 代码如下

    public  int get(int key){int idx = Math.abs(key % arr.length);Node cur = arr[idx];while(cur!=null){if(cur.key == key){return cur.val;}cur = cur.next;}return -1;}

计算负载因子

写一个私有方法,计算负载因子

负载因子（Load Factor）
负载因子是哈希表中元素数量与桶的数量之间的比值。负载因子过高会导致频繁碰撞，从而降低性能。因此，哈希表通常会在负载因子超过某个阈值时进行扩容，增加桶的数量，以保持操作的效率。

    private  float  loadnum(){return usedsize*1.0f/arr.length;}

扩容(难点)

接下来就是我们的扩容,当计算到的负载因子>0.75时,我们就需要扩容,但是扩容要怎么扩?

我给出如下的具体思路

扩容操作的基本思路

创建新数组：我们需要一个新的、更大的数组来存储哈希表中的元素。在这个方法中，新数组的大小是当前数组大小的两倍（arr.length * 2）。
重新计算哈希值：由于哈希表的大小发生了变化，原有的哈希值将不再适用。我们需要根据新的数组大小重新计算每个元素的哈希值，并将元素重新放入新的数组中。
迁移元素：将原数组中的元素逐一移到新的数组中。元素需要根据新的数组大小（即新的桶数）重新定位到适当的位置。

1.扩容

 Node [] newarr = new Node[arr.length*2];

2.遍历旧数组

 for(int i=0;i<arr.length;i++){Node cur = arr[i];

为什么要创建结点呢?因为我们使用了链式法解决哈希冲突,所以每个桶的元素可能是一个链表

3.遍历链表并重新映射元素

            while(cur != null){Node temp = cur.next;int idx = cur.key % newarr.length;// 新的地址cur.next = newarr[idx];newarr[idx] = cur;cur = temp;}

对于每个非空桶（链表），我们遍历该链表并将其中的每个元素（Node cur）从原数组中迁移到新数组中。
重新计算索引：对于每个元素，我们重新计算它在新数组中的位置，使用新的数组长度来计算哈希值（cur.key % newarr.length）。这保证了每个元素被分配到新的桶（槽）中。
重新连接链表：将原来的链表节点（cur）插入到新的数组桶中。由于我们采用链式法（cur.next = newarr[idx]），每次插入的元素都会成为该桶的链表头。
移动到下一个节点：遍历链表，直到遍历完所有的元素（cur = temp）。

4.更新数组

arr = newarr;

我们将原数组 arr 引用指向新的数组 newarr,扩容完成

完整代码

private  void resize(){Node [] newarr = new Node[arr.length*2];for(int i=0;i<arr.length;i++){Node cur = arr[i];while(cur != null){Node temp = cur.next;int idx = cur.key % newarr.length;// 新的地址cur.next = newarr[idx];newarr[idx] = cur;cur = temp;}}arr = newarr;}

完整代码(方便大家复制自己去调试)

数据是int的

public class Hashmap {// 哈希桶 - 数组链表static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}// 建立数组public Node[] arr;public int usedsize;public  static final   float  loadnum = 0.75f;public Hashmap() {this.arr = new Node[10];  // 初始化数组容量为 10}public void put(int key, int val) {int idx = key % arr.length;Node cur = arr[idx];// 如果链表已经存在，检查是否有相同 keywhile (cur != null) {if (cur.key == key) {cur.val = val;  // 更新值return;}cur = cur.next;}// 插入新节点（尾插法）Node newNode = new Node(key, val);// 如果当前桶为空，直接插入if (arr[idx] == null) {arr[idx] = newNode;} else {// 否则，找到链表的尾部插入新节点Node cur2 = arr[idx];while (cur2.next != null) {cur2 = cur2.next;}cur2.next = newNode;}usedsize++;if(loadnum()>loadnum){resize();}}private  void resize(){Node [] newarr = new Node[arr.length*2];for(int i=0;i<arr.length;i++){Node cur = arr[i];while(cur != null){Node temp = cur.next;int idx = cur.key % newarr.length;// 新的地址cur.next = newarr[idx];newarr[idx] = cur;cur = temp;}}arr = newarr;}private  float  loadnum(){return usedsize*1.0f/arr.length;}public  int get(int key){int idx = Math.abs(key % arr.length);Node cur = arr[idx];while(cur!=null){if(cur.key == key){return cur.val;}cur = cur.next;}return -1;}
}

使用泛型实现的

我还写了一个利用泛型实现的,这样可以用在不同类型的数据中

public class Hashmap1<K, V> {// 哈希桶 - 数组链表static class Node<K, V> {public K key;public V val;public Node<K, V> next;public Node(K key, V val) {this.key = key;this.val = val;}}// 建立数组public Node<K, V>[] arr;public int usedsize;public static final float LOAD_FACTOR = 0.75f;// 构造函数，初始化数组容量public Hashmap1() {this.arr = new Node[10]; // 初始化容量为 10}// 插入或更新键值对public void put(K key, V val) {int idx = Math.abs(key.hashCode() % arr.length);  // 使用键的 hashCode() 来计算索引Node<K, V> cur = arr[idx];// 如果链表中存在相同的 key，更新对应的值while (cur != null) {if (cur.key.equals(key)) {cur.val = val;  // 更新值return;}cur = cur.next;}// 插入新节点（尾插法）Node<K, V> newNode = new Node<>(key, val);// 如果当前桶为空，直接插入if (arr[idx] == null) {arr[idx] = newNode;} else {// 否则，找到链表的尾部插入新节点Node<K, V> cur2 = arr[idx];while (cur2.next != null) {cur2 = cur2.next;}cur2.next = newNode;}usedsize++;// 判断是否需要扩容if (loadFactor() > LOAD_FACTOR) {resize();}}// 重新调整哈希表的大小private void resize() {Node<K, V>[] newarr = new Node[arr.length * 2];for (int i = 0; i < arr.length; i++) {Node<K, V> cur = arr[i];while (cur != null) {Node<K, V> temp = cur.next;int idx = Math.abs(cur.key.hashCode() % newarr.length); // 计算新索引cur.next = newarr[idx];newarr[idx] = cur;cur = temp;}}arr = newarr;}// 计算负载因子private float loadFactor() {return usedsize * 1.0f / arr.length;}// 根据键获取值public V get(K key) {int idx = Math.abs(key.hashCode() % arr.length);Node<K, V> cur = arr[idx];while (cur != null) {if (cur.key.equals(key)){System.out.println(key.hashCode());return cur.val;}cur = cur.next;}return null; // 如果没找到，返回 null}
}

结尾

博客还是基本的介绍了一下怎么实现简单的哈希表,希望对于读者有用,也欢迎读者指出我博客中的错误,核实后有偿.

前言

哈希表的概念和诞生的原因

哈希冲突

简单实现哈希表

基本属性

插入

获取key的val

计算负载因子

扩容(难点)

完整代码(方便大家复制自己去调试)

数据是int的

使用泛型实现的

结尾

相关文章：