前文 哈希表核心原理 中我介绍了哈希表的核心原理和几个关键概念,拉链法原理和实现 中介绍了拉链法的实现,线性探查法的两个难点 介绍了线性探查法实现哈希表的难点所在,并给出了两种方法解决删除元素时的空洞问题,本文会同时给出这两种方法的参考代码实现。
本文会先结合可视化面板给出简化的实现,方便大家理解增删查改的过程,最后给完整实现。
简化实现中,具体简化的地方如下:
1、我们实现的哈希表只支持 key
类型为 int
,value
类型为 int
的情况,如果 key
不存在,就返回 -1
。
2、我们实现的 hash
函数就是简单地取模,即 hash(key) = key % table.length
。这样也方便模拟出哈希冲突的情况,比如当 table.length = 10
时,hash(1)
和 hash(11)
的值都是 1。
3、底层的 table
数组的大小在创建哈希表时就固定,假设 table
数组不会被装满,不考虑负载因子和动态扩缩容的问题。
这些简化能够帮助我们聚焦增删查改的核心逻辑,并且可以借助 可视化面板 辅助大家学习理解。
简化版代码
搬移数据的线性探查法
这种方法在 remove
操作时,会将删除的元素后面的元素重新插入哈希表,以此保持元素的连续性。
这里直接给出简化版的代码实现,你可以先看看,后面将通过可视化面板展示增删查改的过程:
// 用线性探查法解决哈希冲突的简化实现(rehash 版)
public class ExampleLinearProbingHashMap1 {
private static class Node {
int key;
int val;
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
// 哈希表的底层数组,每个索引存储一个键值对
private final Node[] table;
public ExampleLinearProbingHashMap1(int cap) {
table = new Node[cap];
}
// 增/改
public void put(int key, int value) {
int index = findKeyIndex(key);
table[index] = new Node(key, value);
}
// 查,找不到就返回 -1
public int get(int key) {
int index = findKeyIndex(key);
return table[index] == null ? -1 : table[index].val;
}
// 删
public void remove(int key) {
int index = findKeyIndex(key);
if (table[index] == null) {
return;
}
table[index] = null;
// 保持元素连续性,搬移数据(这个过程称为 rehash)
index = (index + 1) % table.length;
while (table[index] != null) {
Node entry = table[index];
table[index] = null;
// 这个操作是关键,利用 put 方法,将键值对重新插入
// 这样就能把它们移动到正确的 table 索引位置
put(entry.key, entry.val);
index = (index + 1) % table.length;
}
}
// 线性探测法查找 key 在 table 中的索引
// 如果找不到,返回的就是下一个为 null 的索引,可用于插入
private int findKeyIndex(int key) {
int index = hash(key);
while (table[index] != null) {
if (table[index].key == key) {
return index;
}
// 注意环形数组特性
index = (index + 1) % table.length;
}
return index;
}
private int hash(int key) {
return key % table.length;
}
public static void main(String[] args) {
ExampleLinearProbingHashMap1 map = new ExampleLinearProbingHashMap1(10);
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
System.out.println(map.get(1)); // 1
System.out.println(map.get(2)); // 2
System.out.println(map.get(20)); // 20
map.put(1, 100);
System.out.println(map.get(1)); // 100
map.remove(20);
System.out.println(map.get(20)); // -1
System.out.println(map.get(30)); // 30
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
#include <iostream>
#include <vector>
using namespace std;
// 用线性探查法解决哈希冲突的简化实现(rehash 版)
class Node {
public:
int key;
int val;
Node(int key, int val) {
this->key = key;
this->val = val;
}
};
class ExampleLinearProbingHashMap1 {
private:
// 哈希表的底层数组,每个索引存储一个键值对
vector<Node*> table;
public:
ExampleLinearProbingHashMap1(int cap) {
this->table.resize(cap);
}
// 增/改
void put(int key, int value) {
int index = findKeyIndex(key);
table[index] = new Node(key, value);
}
// 查,找不到就返回 -1
int get(int key) {
int index = findKeyIndex(key);
return table[index] == NULL ? -1 : table[index]->val;
}
// 删
void remove(int key) {
int index = findKeyIndex(key);
if (table[index] == NULL) {
return;
}
table[index] = NULL;
// 保持元素连续性,搬移数据(这个过程称为 rehash)
index = (index + 1) % table.size();
while (table[index] != NULL) {
Node* entry = table[index];
table[index] = NULL;
// 这个操作是关键,利用 put 方法,将键值对重新插入
// 这样就能把它们移动到正确的 table 索引位置
put(entry->key, entry->val);
index = (index + 1) % table.size();
}
}
// 线性探测法查找 key 在 table 中的索引
// 如果找不到,返回的就是下一个为 null 的索引,可用于插入
int findKeyIndex(int key) {
int index = hash(key);
while (table[index] != NULL) {
if (table[index]->key == key) {
return index;
}
// 注意环形数组特性
index = (index + 1) % table.size();
}
return index;
}
int hash(int key) {
return key % table.size();
}
};
int main() {
ExampleLinearProbingHashMap1 map(10);
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
cout << map.get(1) << endl;
cout << map.get(2) << endl;
cout << map.get(20) << endl;
map.put(1, 100);
cout << map.get(1) << endl;
map.remove(20);
cout << map.get(20) << endl;
cout << map.get(30) << endl;
return 0;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
# 用线性探查法解决哈希冲突的简化实现(rehash 版)
class ExampleLinearProbingHashMap1:
def __init__(self, cap):
self.table = [None] * cap
def put(self, key, value):
index = self.findKeyIndex(key)
self.table[index] = Node(key, value)
def get(self, key):
index = self.findKeyIndex(key)
return -1 if self.table[index] is None else self.table[index].val
def remove(self, key):
index = self.findKeyIndex(key)
if self.table[index] is None:
return
self.table[index] = None
index = (index + 1) % len(self.table)
while self.table[index] is not None:
entry = self.table[index]
self.table[index] = None
self.put(entry.key, entry.val)
index = (index + 1) % len(self.table)
def findKeyIndex(self, key):
index = self.hash(key)
while self.table[index] is not None:
if self.table[index].key == key:
return index
index = (index + 1) % len(self.table)
return index
def hash(self, key):
return key % len(self.table)
def main():
map = ExampleLinearProbingHashMap1(10)
map.put(1, 1)
map.put(2, 2)
map.put(10, 10)
map.put(20, 20)
map.put(30, 30)
map.put(3, 3)
print(map.get(1)) # 1
print(map.get(2)) # 2
print(map.get(20)) # 20
map.put(1, 100)
print(map.get(1)) # 100
map.remove(20)
print(map.get(20)) # -1
print(map.get(30)) # 30
if __name__ == "__main__":
main()
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
import "fmt"
//定义节点结构体
type Node struct {
key int
val int
}
//定义哈希表结构体
type ExampleLinearProbingHashMap1 struct {
table []*Node
}
//初始化哈希表
func NewExampleLinearProbingHashMap1(cap int) *ExampleLinearProbingHashMap1 {
table := make([]*Node, cap)
return &ExampleLinearProbingHashMap1{
table: table,
}
}
//增/改
func (e *ExampleLinearProbingHashMap1) Put(key int, value int) {
index := e.findKeyIndex(key)
e.table[index] = &Node{
key: key,
val: value,
}
}
//查,找不到就返回 -1
func (e *ExampleLinearProbingHashMap1) Get(key int) int {
index := e.findKeyIndex(key)
if e.table[index] == nil {
return -1
}
return e.table[index].val
}
// 删
func (e *ExampleLinearProbingHashMap1) Remove(key int) {
index := e.findKeyIndex(key)
if e.table[index] == nil {
return
}
e.table[index] = nil
index = (index + 1) % len(e.table)
while e.table[index] != nil {
tmp := e.table[index]
e.table[index] = nil
// 这个操作是关键,利用 put 方法,将键值对重新插入
// 这样就能把它们移动到正确的 table 索引位置
e.Put(tmp.key, tmp.val)
index = (index + 1) % len(e.table)
}
}
// 线性探测法查找 key 在 table 中的索引
// 如果找不到,返回的就是下一个为 null 的索引,可用于插入
func (e *ExampleLinearProbingHashMap1) findKeyIndex(key int) int {
index := e.hash(key)
for e.table[index] != nil {
if e.table[index].key == key {
return index
}
index = (index + 1) % len(e.table)
}
return index
}
//散列函数
func (e *ExampleLinearProbingHashMap1) hash(key int) int {
return key % len(e.table)
}
func main() {
map1 := NewExampleLinearProbingHashMap1(10)
map1.Put(1, 1)
map1.Put(2, 2)
map1.Put(10, 10)
map1.Put(20, 20)
map1.Put(30, 30)
map1.Put(3, 3)
fmt.Println(map1.Get(1)) // 1
fmt.Println(map1.Get(2)) // 2
fmt.Println(map1.Get(20)) // 20
map1.Put(1, 100)
fmt.Println(map1.Get(1)) // 100
map1.Remove(20)
fmt.Println(map1.Get(20)) // -1
fmt.Println(map1.Get(30)) // 30
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var ExampleLinearProbingHashMap1 = function(cap){
// private static class Node
var Node = function(key, val){
this.key = key;
this.val = val;
}
// 哈希表的底层数组,每个索引存储一个键值对
this.table = new Array(cap);
// 增/改
this.put = function(key, value){
var index = this.findKeyIndex(key);
this.table[index] = new Node(key, value);
}
// 查,找不到就返回 -1
this.get = function(key){
var index = this.findKeyIndex(key);
return this.table[index] === null ? -1 : this.table[index].val;
}
// 删
this.remove = function(key){
var index = this.findKeyIndex(key);
if(this.table[index] === null){
return;
}
this.table[index] = null;
// 保持元素连续性,搬移数据(这个过程称为 rehash)
index = (index + 1) % this.table.length;
while(this.table[index] !== null){
var entry = this.table[index];
this.table[index] = null;
// 这个操作是关键,利用 put 方法,将键值对重新插入
// 这样就能把它们移动到正确的 table 索引位置
this.put(entry.key, entry.val);
index = (index + 1) % this.table.length;
}
}
// 线性探测法查找 key 在 table 中的索引
// 如果找不到,返回的就是下一个为 null 的索引,可用于插入
this.findKeyIndex = function(key){
var index = this.hash(key);
while(this.table[index] !== null){
if(this.table[index].key === key){
return index;
}
// 注意环形数组特性
index = (index + 1) % this.table.length;
}
return index;
}
this.hash = function(key){
return key % this.table.length;
}
}
var main = function(){
var map = new ExampleLinearProbingHashMap1(10);
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
console.log(map.get(1)); // 1
console.log(map.get(2)); // 2
console.log(map.get(20)); // 20
map.put(1, 100);
console.log(map.get(1)); // 100
map.remove(20);
console.log(map.get(20)); // -1
console.log(map.get(30)); // 30
}
main();
特殊占位符的线性探查法
这种方法通过一个 DELETED
特殊值作为占位符,标记被删除的元素。
这个方法与上面的方法最大的区别在于 findKeyIndex
方法的实现,同时需要对 DELETED
特殊处理。直接看代码吧,后面会通过可视化面板展示增删查改的过程:
// 用线性探查法解决哈希冲突的简化实现(特殊占位符版)
public class ExampleLinearProbingHashMap2 {
private static class KVNode {
int key;
int val;
public KVNode(int key, int val) {
this.key = key;
this.val = val;
}
}
// 用于标记被删元素的占位符
// 里面的值可以随意存储,因为只会使用 == 判断指针相等,不用比较里面的值
private final KVNode DELETED = new KVNode(-2, -2);
// 真正存储键值对的数组
private final KVNode[] table;
public ExampleLinearProbingHashMap2(int initCapacity) {
table = new KVNode[initCapacity];
}
// 增/改
public void put(int key, int val) {
int index = findKeyIndex(key);
if (index != -1) {
// key 已存在,修改对应的 val
KVNode node = table[index];
if (node != null) {
node.val = val;
return;
}
}
// key 不存在
KVNode node = new KVNode(key, val);
// 在 table 中找一个空位或者占位符进行插入
index = hash(key);
while (table[index] != null && table[index] != DELETED) {
index = (index + 1) % table.length;
}
table[index] = node;
}
// 删
public void remove(int key) {
int index = findKeyIndex(key);
if (index == -1) {
// key 不存在,不需要 remove
return;
}
// 直接用占位符表示删除
table[index] = DELETED;
}
// 查,返回 key 对应的 val,如果 key 不存在,则返回 -1
public int get(int key) {
int index = findKeyIndex(key);
if (index == -1) {
return -1;
}
return table[index].val;
}
// 线性探测法查找 key 在 table 中的索引
// 如果找不到,返回 -1
private int findKeyIndex(int key) {
// 因为删除元素时只是标记为 DELETED,并不是真的删除
// 所以 table 可能会被填满,导致死循环
// step 用来记录查找的步数,防止死循环
int step = 0;
// 注意环形数组特性
for (int i = hash(key); table[i] != null; i = (i + 1) % table.length) {
if (table[i] == DELETED) {
// 遇到占位符直接跳过
continue;
}
if (table[i].key == key) {
return i;
}
step++;
// 防止死循环
if (step == table.length) {
return -1;
}
}
return -1;
}
// 哈希函数,将键映射到 table 的索引
private int hash(int key) {
return key % table.length;
}
public static void main(String[] args) {
ExampleLinearProbingHashMap2 map = new ExampleLinearProbingHashMap2(10);
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
System.out.println(map.get(1)); // 1
System.out.println(map.get(2)); // 2
System.out.println(map.get(20)); // 20
map.put(1, 100);
System.out.println(map.get(1)); // 100
map.remove(20);
System.out.println(map.get(20)); // -1
System.out.println(map.get(30)); // 30
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
#include <iostream>
#include <vector>
// 用线性探查法解决哈希冲突的简化实现(特殊占位符版)
// Special placeholder for deleted elements.
// 用于标记被删元素的占位符
struct KVNode {
int key;
int val;
};
class ExampleLinearProbingHashMap2 {
private:
// 真正存储键值对的数组
std::vector<KVNode*> table;
// 里面的值可以随意存储,因为只会使用 == 判断指针相等,不用比较里面的值
KVNode* DELETED = new KVNode{-2, -2};
// 哈希函数,将键映射到 table 的索引
int hash(int key) {
return key % table.size();
}
// 线性探测法查找 key 在 table 中的索引,如果找不到,返回 -1
int findKeyIndex(int key) {
// 因为删除元素时只是标记为 DELETED,并不是真的删除,所以 table 可能会被填满,导致死循环
// step 用来记录查找的步数,防止死循环
for (int i = hash(key), step = 0; table[i] != nullptr; i = (i+1) % table.size()) {
// 遇到占位符直接跳过
if (table[i] == DELETED) continue;
if (table[i]->key == key) return i;
if (++step == table.size()) return -1;
}
return -1;
}
public:
// 构造函数,初始化哈希表容量
explicit ExampleLinearProbingHashMap2(int initCapacity) {
table.resize(initCapacity, nullptr);
}
// 增/改
void put(int key, int val) {
int index = findKeyIndex(key);
// key 已存在,修改对应的 val,如果 key 不存在,新建节点并插入表中
if (index != -1 && table[index] != nullptr) {
table[index]->val = val;
return;
}
KVNode* node = new KVNode{key, val};
index = hash(key);
while (table[index] != nullptr && table[index] != DELETED) {
index = (index+1) % table.size();
}
table[index] = node;
}
// 删
void remove(int key) {
int index = findKeyIndex(key);
// key 不存在,不需要 remove
if (index == -1) return;
// 直接用占位符表示删除
table[index] = DELETED;
}
// 查,返回 key 对应的 val,如果 key 不存在,则返回 -1
int get(int key) {
int index = findKeyIndex(key);
return (index != -1) ? table[index]->val : -1;
}
};
int main() {
ExampleLinearProbingHashMap2 map(10);
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
std::cout << map.get(1) << std::endl; // Output: 1
std::cout << map.get(2) << std::endl; // Output: 2
std::cout << map.get(20) << std::endl; // Output: 20
map.put(1, 100);
std::cout << map.get(1) << std::endl; // Output: 100
map.remove(20);
std::cout << map.get(20) << std::endl; // Output: -1
std::cout << map.get(30) << std::endl; // Output: 30
return 0;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# 用线性探查法解决哈希冲突的简化实现(特殊占位符版)
class ExampleLinearProbingHashMap2:
class KVNode:
def __init__(self, key, val):
self.key = key
self.val = val
# 用于标记被删元素的占位符
DELETED = KVNode(-2, -2)
# 真正存储键值对的数组
def __init__(self, init_capacity):
self.table = [None] * init_capacity
# 增/改
def put(self, key, val):
index = self.find_key_index(key)
if index != -1:
node = self.table[index]
if node is not None:
node.val = val
return
# key 不存在
node = self.KVNode(key, val)
# 在 table 中找一个空位或者占位符进行插入
index = self.hash(key)
while self.table[index] is not None and self.table[index] != self.DELETED:
index = (index + 1) % len(self.table)
self.table[index] = node
# 删
def remove(self, key):
index = self.find_key_index(key)
if index == -1:
# key 不存在,不需要 remove
return
# 直接用占位符表示删除
self.table[index] = self.DELETED
# 查,返回 key 对应的 val,如果 key 不存在,则返回 -1
def get(self, key):
index = self.find_key_index(key)
if index == -1:
return -1
return self.table[index].val
# 线性探测法查找 key 在 table 中的索引
# 如果找不到,返回 -1
def find_key_index(self, key):
step = 0
for i in range(self.hash(key), len(self.table)):
if self.table[i] == self.DELETED:
continue
if self.table[i] and self.table[i].key == key:
return i
# 防止死循环
step += 1
if step == len(self.table):
return -1
return -1
# 哈希函数,将键映射到 table 的索引
def hash(self, key):
return key % len(self.table)
# Testing the class
map = ExampleLinearProbingHashMap2(10)
map.put(1, 1)
map.put(2, 2)
map.put(10, 10)
map.put(20, 20)
map.put(30, 30)
map.put(3, 3)
print(map.get(1)) # 1
print(map.get(2)) # 2
print(map.get(20)) # 20
map.put(1, 100)
print(map.get(1)) # 100
map.remove(20)
print(map.get(20)) # -1
print(map.get(30)) # 30
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
import (
"fmt"
)
// KVNode 定义了存储在哈希表中的键值对结构
type KVNode struct {
key int
val int
}
// ExampleLinearProbingHashMap2: 用线性探查法解决哈希冲突的简化实现(特殊占位符版)
type ExampleLinearProbingHashMap2 struct {
DELETED *KVNode
table []*KVNode
}
// 创建新的哈希表实例
func NewExampleLinearProbingHashMap2(initCapacity int) *ExampleLinearProbingHashMap2 {
m := &ExampleLinearProbingHashMap2{
DELETED: &KVNode{-2, -2}, // 使用特殊占位符表示已删除的元素
table: make([]*KVNode, initCapacity),
}
return m
}
// 增/改操作
func (m *ExampleLinearProbingHashMap2) put(key int, val int) {
index := m.findKeyIndex(key)
if index != -1 {
// key 已存在,修改对应的 val
node := m.table[index]
if node != nil {
node.val = val
return
}
}
// key 不存在, 创建新的 KVNode
node := &KVNode{key, val}
// 在 table 中找一个空位或者占位符进行插入
index = m.hashFunc(key)
for m.table[index] != nil && m.table[index] != m.DELETED {
index = (index + 1) % len(m.table)
}
m.table[index] = node
}
// 删操作
func (m *ExampleLinearProbingHashMap2) remove(key int) {
index := m.findKeyIndex(key)
if index == -1 {
// key 不存在,不需要 remove
return
}
// 直接用占位符表示删除
m.table[index] = m.DELETED
}
// 查,返回 key 对应的 val,如果 key 不存在,则返回 -1
func (m *ExampleLinearProbingHashMap2) get(key int) int {
index := m.findKeyIndex(key)
if index == -1 {
return -1
}
return m.table[index].val
}
// 线性探测法查找 key 在 table 中的索引
// 如果找不到,返回 -1
func (m *ExampleLinearProbingHashMap2) findKeyIndex(key int) int {
// 因为删除元素时只是标记为 DELETED,并不是真的删除
// 所以 table 可能会被填满,导致死循环
// step 用来记录查找的步数,防止死循环
step := 0
// 注意环形数组特性
for i := m.hashFunc(key); m.table[i] != nil; i = (i + 1) % len(m.table) {
if m.table[i] == m.DELETED {
// 遇到占位符直接跳过
continue
}
if m.table[i].key == key {
return i
}
step++
// 防止死循环
if step == len(m.table) {
return -1
}
}
return -1
}
// 哈希函数,将键映射到 table 的索引
func (m *ExampleLinearProbingHashMap2) hashFunc(key int) int {
return key % len(m.table)
}
func main() {
// 创建一个新的哈希表实例
mapInstance := NewExampleLinearProbingHashMap2(10)
mapInstance.put(1, 1)
mapInstance.put(2, 2)
mapInstance.put(10, 10)
mapInstance.put(20, 20)
mapInstance.put(30, 30)
mapInstance.put(3, 3)
fmt.Println(mapInstance.get(1)) // 1
fmt.Println(mapInstance.get(2)) // 2
fmt.Println(mapInstance.get(20)) // 20
// 修改键 1 的值
mapInstance.put(1, 100)
fmt.Println(mapInstance.get(1)) // 100
// 删除键为 20 的元素
mapInstance.remove(20)
fmt.Println(mapInstance.get(20)) // -1
fmt.Println(mapInstance.get(30)) // 30
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 用线性探查法解决哈希冲突的简化实现(特殊占位符版)
var ExampleLinearProbingHashMap2 = function(initCapacity) {
var DELETED = {key: -2, val: -2};
var table = new Array(initCapacity);
var KVNode = function(key, val) {
this.key = key;
this.val = val;
};
var hash = function(key) {
return key % table.length;
};
var findKeyIndex = function(key) {
var step = 0;
for (var i = hash(key); table[i] !== null; i = (i + 1) % table.length) {
if (table[i] === DELETED) {
continue;
}
if (table[i].key === key) {
return i;
}
step++;
if (step === table.length) {
return -1;
}
}
return -1;
};
this.put = function(key, val) {
var index = findKeyIndex(key);
if (index !== -1) {
var node = table[index];
if (node !== null) {
node.val = val;
return;
}
}
var node = new KVNode(key, val);
index = hash(key);
while (table[index] !== null && table[index] !== DELETED) {
index = (index + 1) % table.length;
}
table[index] = node;
};
this.remove = function(key) {
var index = findKeyIndex(key);
if (index === -1) {
return;
}
table[index] = DELETED;
};
this.get = function(key) {
var index = findKeyIndex(key);
if (index === -1) {
return -1;
}
return table[index].val;
};
};
var map = new ExampleLinearProbingHashMap2(10);
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
console.log(map.get(1)); // 1
console.log(map.get(2)); // 2
console.log(map.get(20)); // 20
map.put(1, 100);
console.log(map.get(1)); // 100
map.remove(20);
console.log(map.get(20)); // -1
console.log(map.get(30)); // 30
完整版代码
有了上面的铺垫,我们现在来看比较完善的 Java 代码实现,主要新增了以下几个功能:
1、使用了泛型,可以存储任意类型的 key
和 value
。
2、底层的 table
数组会根据负载因子动态扩缩容。
3、使用了 哈希表基础 中提到的 hash
函数,利用 key
的 hashCode()
方法和 table.length
来计算哈希值。
4、实现了 keys()
方法,可以返回哈希表中所有的 key
。
下面我会分别给出 rehash 版本和特殊值标记版本的实现,具体细节可以参考代码注释。
rehash 版本
import java.util.LinkedList;
import java.util.List;
// rehash 方式实现的线性探查哈希表
public class MyLinearProbingHashMap1<K, V> {
private static class KVNode<K, V> {
K key;
V val;
KVNode(K key, V val) {
this.key = key;
this.val = val;
}
}
// 真正存储键值对的数组
private KVNode<K, V>[] table;
// HashMap 中的键值对个数
private int size;
// 默认的初始化容量
private static final int INIT_CAP = 4;
public MyLinearProbingHashMap1() {
this(INIT_CAP);
}
public MyLinearProbingHashMap1(int initCapacity) {
size = 0;
table = (KVNode<K, V>[]) new KVNode[initCapacity];
}
/***** 增/改 *****/
public void put(K key, V val) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
// 我们把负载因子默认设为 0.75,超过则扩容
if (size >= table.length * 0.75) {
resize(table.length * 2);
}
int index = getKeyIndex(key);
// key 已存在,修改对应的 val
if (table[index] != null) {
table[index].val = val;
return;
}
// key 不存在,在空位插入
table[index] = new KVNode<>(key, val);
size++;
}
/***** 删 *****/
// 删除 key 和对应的 val
public void remove(K key) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
// 缩容,当负载因子小于 0.125 时,缩容
if (size <= table.length / 8) {
resize(table.length / 4);
}
int index = getKeyIndex(key);
if (table[index] == null) {
// key 不存在,不需要 remove
return;
}
// 开始 remove
table[index] = null;
size--;
// 保持元素连续性,进行 rehash
index = (index + 1) % table.length;
for (; table[index] != null; index = (index + 1) % table.length) {
KVNode<K, V> entry = table[index];
table[index] = null;
// 这里减一,因为 put 里面又会加一
size--;
put(entry.key, entry.val);
}
}
/***** 查 *****/
// 返回 key 对应的 val,如果 key 不存在,则返回 null
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
int index = getKeyIndex(key);
if (table[index] == null) {
return null;
}
return table[index].val;
}
// 返回所有 key(顺序不固定)
public List<K> keys() {
LinkedList<K> keys = new LinkedList<>();
for (KVNode<K, V> entry : table) {
if (entry != null) {
keys.addLast(entry.key);
}
}
return keys;
}
/***** 其他工具函数 *****/
public int size() {
return size;
}
// 哈希函数,将键映射到 table 的索引
// [0, table.length - 1]
private int hash(K key) {
// int: 0000 0000 0000 ... 0000
// : 0111 1111 1111 ... 1111
return (key.hashCode() & 0x7fffffff) % table.length;
}
// 对 key 进行线性探查,返回一个索引
// 如果 key 不存在,返回的就是下一个为 null 的索引,可用于插入
private int getKeyIndex(K key) {
int index;
for (index = hash(key); table[index] != null; index = (index + 1) % table.length) {
if (table[index].key.equals(key))
return index;
}
return index;
}
private void resize(int newCap) {
MyLinearProbingHashMap1<K, V> newMap = new MyLinearProbingHashMap1<>(newCap);
for (KVNode<K, V> entry : table) {
if (entry != null) {
newMap.put(entry.key, entry.val);
}
}
this.table = newMap.table;
}
public static void main(String[] args) {
MyLinearProbingHashMap1<Integer, Integer> map = new MyLinearProbingHashMap1<>();
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
System.out.println(map.get(1)); // 1
System.out.println(map.get(2)); // 2
System.out.println(map.get(20)); // 20
map.put(1, 100);
System.out.println(map.get(1)); // 100
map.remove(20);
System.out.println(map.get(20)); // null
System.out.println(map.get(30)); // 30
}
}
特殊值标记版本
import java.util.LinkedList;
import java.util.List;
public class MyLinearProbingHashMap2<K, V> {
private static class KVNode<K, V> {
K key;
V val;
KVNode(K key, V val) {
this.key = key;
this.val = val;
}
}
// 被删除的 KVNode 的占位符
private final KVNode<K, V> DUMMY = new KVNode<>(null, null);
// 真正存储键值对的 table 数组
private KVNode<K, V>[] table;
// HashMap 中的键值对个数
private int size;
// 默认的初始化容量
private static final int INIT_CAP = 4;
public MyLinearProbingHashMap2() {
this(INIT_CAP);
}
public MyLinearProbingHashMap2(int cap) {
size = 0;
table = (KVNode<K, V>[]) new KVNode[cap];
}
/***** 增/改 *****/
// 添加 key -> val 键值对
// 如果键 key 已存在,则将值修改为 val
public void put(K key, V val) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
// 负载因子默认设为 0.75,超过则扩容
if (size >= table.length * 0.75) {
resize(table.length * 2);
}
int index = getKeyIndex(key);
if (index != -1) {
// key 已存在,修改对应的 val
table[index].val = val;
return;
}
// key 不存在
KVNode<K, V> x = new KVNode<>(key, val);
// 在 table 中找一个空位或者占位符,插入
index = hash(key);
while (table[index] != null && table[index] != DUMMY) {
index = (index + 1) % table.length;
}
table[index] = x;
size++;
}
/***** 删 *****/
// 删除 key 和对应的 val,并返回 val
// 若 key 不存在,则返回 null
public void remove(K key) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
// 缩容
if (size < table.length / 8) {
resize(table.length / 2);
}
int index = getKeyIndex(key);
if (index == -1) {
// key 不存在,不需要 remove
return;
}
// 开始 remove
// 直接用占位符表示删除
table[index] = DUMMY;
size--;
}
/***** 查 *****/
// 返回 key 对应的 val
// 如果 key 不存在,则返回 null
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException("key is null");
}
int index = getKeyIndex(key);
if (index == -1) {
return null;
}
return table[index].val;
}
public List<K> keys() {
LinkedList<K> keys = new LinkedList<>();
for (KVNode<K, V> entry : table) {
if (entry != null) {
keys.addLast(entry.key);
}
}
return keys;
}
public int size() {
return size;
}
// 对 key 进行线性探查,返回一个索引
// 根据 keys[i] 是否为 null 判断是否找到对应的 key
private int getKeyIndex(K key) {
int step = 0;
for (int i = hash(key); table[i] != null; i = (i + 1) % table.length) {
KVNode<K, V> entry = table[i];
// 遇到占位符直接跳过
if (entry == DUMMY) {
continue;
}
if (entry.key.equals(key)) {
return i;
}
step++;
// 防止死循环
if (step == table.length) {
// 这里可以触发一次 resize,把标记为删除的占位符清理掉
resize(table.length);
return -1;
}
}
return -1;
}
// 哈希函数,将键映射到 table 的索引
// [0, table.length - 1]
private int hash(K key) {
// int: 0000 0000 0000 ... 0000
// : 0111 1111 1111 ... 1111
return (key.hashCode() & 0x7fffffff) % table.length;
}
private void resize(int cap) {
MyLinearProbingHashMap2<K, V> newMap = new MyLinearProbingHashMap2<>(cap);
for (KVNode<K, V> entry : table) {
if (entry != null && entry != DUMMY) {
newMap.put(entry.key, entry.val);
}
}
this.table = newMap.table;
}
public static void main(String[] args) {
MyLinearProbingHashMap2<Integer, Integer> map = new MyLinearProbingHashMap2<>();
map.put(1, 1);
map.put(2, 2);
map.put(10, 10);
map.put(20, 20);
map.put(30, 30);
map.put(3, 3);
System.out.println(map.get(1)); // 1
System.out.println(map.get(2)); // 2
System.out.println(map.get(20)); // 20
map.put(1, 100);
System.out.println(map.get(1)); // 100
map.remove(20);
System.out.println(map.get(20)); // null
System.out.println(map.get(30)); // 30
}
}