实现哈希表代码, 使用哈希桶方式解决哈希冲突
// 通过开散列的方式来处理 hash 冲突
public class MyHashMap {
static class Node {
private int key;
private int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
// array 是 hash 表的本体. 数组的每个元素又是一个链表的头结点.
private Node[] array = new Node[101];
private int size = 0; // 表示当前 hash 表中的元素个数
private static final double LOAD_FACTOR = 0.75;
private int hashFunc(int key) {
return key % array.length;
}
// 如果 key 存在, 修改当前 value 的值.
// 如果 key 不存在, 插入新的键值对.
public void put(int key, int value) {
// 1. 需要把 key 映射成数组下标
int index = hashFunc(key);
// 2. 根据下标找到对应的链表
Node list = array[index];
// 3. 当前 key 在链表中是否存在
for (Node cur = list; cur != null; cur = cur.next) {
if (cur.key == key) {
cur.value = value;
return;
}
}
// 4. 循环结束还没找到相同 key 的节点, 直接插入到指定链表头部
Node newNode = new Node(key, value);
newNode.next = list;
array[index] = newNode;
size++;
if (size / array.length > LOAD_FACTOR) {
resize();
}
}
private void resize() {
Node[] newArray = new Node[array.length * 2];
// 把原来 hash 表中所有元素搬运到新数组中.
for (int i = 0; i < array.length; i++) {
for (Node cur = array[i]; cur != null; cur = cur.next) {
int index = cur.key % newArray.length;
Node newNode = new Node(cur.key, cur.value);
newNode.next = newArray[index];
newArray[index] = newNode;
}
}
// 让新数组代替原来的数组.
array = newArray;
}
public Integer get(int key) {
int index = hashFunc(key);
Node list = array[index];
for (Node cur = list;cur != null; cur = cur.next) {
if (cur.key == key) {
return cur.value;
}
}
return null;
}
public void remove(int key) {
int index = hashFunc(key);
if (array[index] == null) {
return;
}
Node list = array[index];
if (list.key == key) {
array[index] = array[index].next;
}
for (Node cur = list.next; cur != null; cur = cur.next) {
if (cur.key == key) {
list.next = cur.next;
}
list = list.next;
}
}
}