Java 中的重新哈希

2025年3月17日 | 阅读 10 分钟

在数据结构中，哈希是最重要的概念，用于将给定的键转换为另一个值。可以使用哈希函数生成新值。

在本节中，我们将结合负载因子和哈希概念来理解Java 中的 Rehash。

Rehash

Rehash 是一种动态扩展 Map、Array 和 Hashtable 大小的技术，以保持 O(1) 的 get 和 put 操作复杂度。

它也可以定义为rehash 是在 map 中的元素数量达到最大阈值时，重新计算已存储条目的哈希码并将其移动到更大尺寸的哈希 map 的过程。

简单来说，rehash 是哈希过程的逆过程。它保留了性能。在 rehash 中，负载因子起着至关重要的作用。

负载因子

负载因子 是一个决定何时增加 HashMap 或 Hashtable 容量的度量，以保持 O(1) 复杂度的get() 和 put() 操作。 HashMap 的负载因子的默认值为 0.75（map 大小的 75%）。简而言之，我们可以说负载因子决定了“何时增加桶的数量来存储键值对”。

较大的负载因子：空间消耗较低，但查找次数较多。较小的负载因子：与所需元素数量相比，空间消耗较大。

如何计算负载因子？

可以使用以下公式计算负载因子

例如

HashMap 的初始容量 = 16
HashMap 的默认负载因子 = 0.75
根据公式：16*0.75 = 12

这表示 HashMap 的第 12 个键值对将保持其大小为 16。一旦第 13 个元素（键值对）进入 HashMap，它将把大小从默认的 2⁴ = 16 个桶增加到 2⁵ = 32 个桶。

负载因子示例

让我们通过一个例子来理解负载因子。

我们知道 HashMap 的默认桶大小为 16。我们插入第一个元素，然后检查是否需要增加 HashMap 容量。这可以通过以下公式确定

HashMap 的大小 (m) / 桶的数量 (n)

在这种情况下，HashMap 的大小是 1，桶的大小是 16。所以，1/16 = 0.0625。现在将获得的值与默认负载因子 (0.75) 进行比较。

0.0625 < 0.75

该值小于默认负载因子的值。因此，无需增加 HashMap 的大小。因此，在第 12 个元素之前，我们不需要增加 HashMap 的大小，因为

12/16 = 0.75

获得的值等于默认负载因子，即 0.75。

一旦我们在 HashMap 中插入第 13 个元素，HashMap 的大小就会增加，因为

13/16 = 0.8125

这里，获得的值大于默认负载因子值。

0.8125 > 0.75

为了将第 13 个元素插入 HashMap，我们需要增加 HashMap 的大小。

如果您想将 get() 和 put() 操作的复杂度保持为 O(1)，建议将负载因子设置在 0.75 左右。

为什么需要 Rehash？

当负载因子增加时，需要 Rehash。当我们向 map 中插入键值对时，负载因子会增加，这也会增加时间复杂度。通常，HashMap 的时间复杂度为 O(1)。为了降低 HashMap 的时间复杂度和负载因子，我们实现了 rehash 技术。

在以下条件下，我们应该使用 rehash

当表已满一半时。
当负载达到某个级别时（负载 > 1/2）。
当插入失败时。
启发式地选择一个负载因子阈值，当阈值被突破时进行 rehash。

实现 Rehash

要实现 rehash 过程，必须遵循以下步骤

对于向 Map 中插入的每个新元素，检查负载因子。
如果负载因子大于其默认值 (0.75)，则实现 rehash。
创建一个大小加倍的新 bucketArray（即前一个数组大小的两倍）。
遍历旧 bucketArray 的每个元素，并为每个元素调用 insert() 方法。insert() 方法将所有元素插入到新创建的、尺寸更大的 bucketArray 中。

由于 N 个元素的 rehash 成本将是

Rehash Java 程序

让我们在 Java 程序中实现 rehash 技术。

RehashingExample.java

import java.util.ArrayList;
class Map<K, V> 
{
class MapNode<K, V> 
{
K key;
V value;
MapNode<K, V> next;
//creating a construtor of the MapNode class
public MapNode(K key, V value)
{
this.key = key;
this.value = value;
next = null;
}
}
//creating a bucket array that stores key-value pairs
ArrayList<MapNode<K, V> > buckets;
//variable denotes the number of pairs stored in bucket array - n
int size;
//variable that denotes the size of the bucketArray - b
int numBuckets;
//defining the default loadFactor
final double DEFAULT_LOAD_FACTOR = 0.75;
//creating a construtor of the Map class
public Map()
{
//defining the size of the bucket    
numBuckets = 5;
buckets = new ArrayList<>(numBuckets);
//loop executes upto number of bucket size and sets nodes initially to null
for (int i = 0; i < numBuckets; i++) 
{
//initially bucket is null
buckets.add(null);
}
//prints all the values that are initially set
System.out.println("HashMap created");
System.out.println("Number of pairs in the Map: " + size);
System.out.println("Size of Map: " + numBuckets);
System.out.println("Default Load Factor : " + DEFAULT_LOAD_FACTOR + "\n");
}
private int getBucketInd(K key)
{
//getting the hash code of the corresponding key by invoking the Object class hashCode() method
int hashCode = key.hashCode();
//calculating the array index and returning the same
return (hashCode % numBuckets);
}
//creating a function that inserts elements to the list
public void insert(K key, V value)
{
//Getting the index at which it needs to be inserted
int bucketInd = getBucketInd(key);
// The first node at that index
MapNode<K, V> head = buckets.get(bucketInd);
// First, loop through all the nodes present at that index
// to check if the key already exists
//the loop iterate over all the nodes presented at that index and checks if the key already exists or not
while (head != null) 
{
//if the key is already presented, the value is updated
if (head.key.equals(key)) 
{
head.value = value;
return;
}
head = head.next;
}
//creating a new node with key-value pair
MapNode<K, V> newElementNode = new MapNode<K, V>(key, value);
// The head node at the index
head = buckets.get(bucketInd);
// the new node is inserted
// by making it the head
		// and it's next is the previous head
newElementNode.next = head;
buckets.set(bucketInd, newElementNode);
System.out.println("Pair(" + key + ", " + value + ") inserted successfully.\n");
// Incrementing size
// as new K-V pair is added to the map
size++;
//calculating the load factor
double loadFactor = (1.0 * size) / numBuckets;
System.out.println("Current Load factor = " + loadFactor);
//if the calculated load factor is greater than the default load factor i.e.0.75, the rehashing is done
if (loadFactor > DEFAULT_LOAD_FACTOR) 
{
System.out.println(loadFactor + " is greater than " + DEFAULT_LOAD_FACTOR);
System.out.println("Therefore Rehashing will be done.\n");
//calling the rehash() function
rehash();
System.out.println("New Size of Map: " + numBuckets + "\n");
}
System.out.println("Number of pairs in the Map: " + size);
System.out.println("Size of Map: " + numBuckets + "\n");
}
//function that performs rehashing
private void rehash()
{
System.out.println("\n***Rehashing Started***\n");
//the present bucket list is made temporarly 
ArrayList<MapNode<K, V> > temp = buckets;
//creating a new bucket list of doubled size of the old bucket size i.e. (2 * numBuckets)
buckets = new ArrayList<MapNode<K, V> >(2 * numBuckets);
for (int i = 0; i < 2 * numBuckets; i++) 
{
//initially all elements set to null
buckets.add(null);
}
// Now size is made zero
// and we loop through all the nodes in the original bucket list(temp)
// and insert it into the new list
size = 0;
numBuckets = numBuckets * 2;
for (int i = 0; i < temp.size(); i++) 
{
// head of the chain at that index
MapNode<K, V> head = temp.get(i);
while (head != null) 
{
K key = head.key;
V val = head.value;
// calling the insert function for each node in temp
// as the new list is now the bucketArray
insert(key, val);
head = head.next;
}
}
System.out.println("\n***Rehashing Done***\n");
}
//method to print the map key-value pairs
public void printMap()
{
//creating a temporary bucket list 
ArrayList<MapNode<K, V> > temp = buckets;
System.out.println("Current HashMap:");
//loop iterate over the Map 
for (int i = 0; i < temp.size(); i++) 
{
//getting the head index of the temporary bucket list
MapNode<K, V> head = temp.get(i);
while (head != null) 
{
System.out.println("key = " + head.key + ", val = " + head.value);
head = head.next;
}
}
System.out.println();
}
}
//main class
public class RehashingExample 
{
public static void main(String args[])
{
//creating the instance of the Map class
Map<Integer, String> map = new Map<Integer, String>();
//adding elements to the Map
map.insert(1, "Hyundai");
map.printMap();
map.insert(2, "KIA");
map.printMap();
map.insert(3, "Toyota");
map.printMap();
map.insert(4, "Mahindra");
map.printMap();
map.insert(5, "Jeep");
map.printMap();
map.insert(6, "Ford");
map.printMap();
map.insert(7, "BMW");
map.printMap();
map.insert(8, "Audi"); 
map.printMap();
map.insert(9, "Mercedes-Benz"); 
map.printMap();
map.insert(10, "Ferrari"); 
map.printMap();
}
} 

输出

HashMap created
Number of pairs in the Map: 0
Size of Map: 5
Default Load Factor : 0.75

Pair(1, Hyundai) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 1
Size of Map: 5

Current HashMap:
key = 1, val = Hyundai

Pair(2, KIA) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 2
Size of Map: 5

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA

Pair(3, Toyota) inserted successfully.

Current Load factor = 0.6
Number of pairs in the Map: 3
Size of Map: 5

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota

Pair(4, Mahindra) inserted successfully.

Current Load factor = 0.8
0.8 is greater than 0.75
Therefore Rehashing will be done.


***Rehashing Started***

Pair(1, Hyundai) inserted successfully.

Current Load factor = 0.1
Number of pairs in the Map: 1
Size of Map: 10

Pair(2, KIA) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 2
Size of Map: 10

Pair(3, Toyota) inserted successfully.

Current Load factor = 0.3
Number of pairs in the Map: 3
Size of Map: 10

Pair(4, Mahindra) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 4
Size of Map: 10


***Rehashing Done***

New Size of Map: 10

Number of pairs in the Map: 4
Size of Map: 10

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra

Pair(5, Jeep) inserted successfully.

Current Load factor = 0.5
Number of pairs in the Map: 5
Size of Map: 10

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra
key = 5, val = Jeep

Pair(6, Ford) inserted successfully.

Current Load factor = 0.6
Number of pairs in the Map: 6
Size of Map: 10

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra
key = 5, val = Jeep
key = 6, val = Ford

Pair(7, BMW) inserted successfully.

Current Load factor = 0.7
Number of pairs in the Map: 7
Size of Map: 10

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra
key = 5, val = Jeep
key = 6, val = Ford
key = 7, val = BMW

Pair(8, Audi) inserted successfully.

Current Load factor = 0.8
0.8 is greater than 0.75
Therefore Rehashing will be done.


***Rehashing Started***

Pair(1, Hyundai) inserted successfully.

Current Load factor = 0.05
Number of pairs in the Map: 1
Size of Map: 20

Pair(2, KIA) inserted successfully.

Current Load factor = 0.1
Number of pairs in the Map: 2
Size of Map: 20

Pair(3, Toyota) inserted successfully.

Current Load factor = 0.15
Number of pairs in the Map: 3
Size of Map: 20

Pair(4, Mahindra) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 4
Size of Map: 20

Pair(5, Jeep) inserted successfully.

Current Load factor = 0.25
Number of pairs in the Map: 5
Size of Map: 20

Pair(6, Ford) inserted successfully.

Current Load factor = 0.3
Number of pairs in the Map: 6
Size of Map: 20

Pair(7, BMW) inserted successfully.

Current Load factor = 0.35
Number of pairs in the Map: 7
Size of Map: 20

Pair(8, Audi) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 8
Size of Map: 20


***Rehashing Done***

New Size of Map: 20

Number of pairs in the Map: 8
Size of Map: 20

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra
key = 5, val = Jeep
key = 6, val = Ford
key = 7, val = BMW
key = 8, val = Audi

Pair(9, Mercedes-Benz) inserted successfully.

Current Load factor = 0.45
Number of pairs in the Map: 9
Size of Map: 20

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra
key = 5, val = Jeep
key = 6, val = Ford
key = 7, val = BMW
key = 8, val = Audi
key = 9, val = Mercedes-Benz

Pair(10, Ferrari) inserted successfully.

Current Load factor = 0.5
Number of pairs in the Map: 10
Size of Map: 20

Current HashMap:
key = 1, val = Hyundai
key = 2, val = KIA
key = 3, val = Toyota
key = 4, val = Mahindra
key = 5, val = Jeep
key = 6, val = Ford
key = 7, val = BMW
key = 8, val = Audi
key = 9, val = Mercedes-Benz
key = 10, val = Ferrari

下一主题Java 中的轮转调度程序

← 上一个下一个 →

Java 中的重新哈希

Rehash

负载因子

负载因子示例

为什么需要 Rehash？

实现 Rehash

Rehash Java 程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的重新哈希

Rehash

负载因子

负载因子示例

为什么需要 Rehash？

实现 Rehash

Rehash Java 程序

相关帖子

Java Program to Find the Missing Element in a Given Permutation

Java 中的 Logger 类

Why We Use Constructor in Java

Types of Inheritance in Java

Reader read(char[]) method in Java with Examples

Java 中的 Stdin 和 Stdout

Java 中的排列系数

Bucket Sort in Java

Java 8 之后的接口 vs. 抽象类

Banker's Algorithm Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器