|
面试的时候难免遇到手撕哈希表的问题，这里进行一些总结。
设计哈希表
力扣地址
简易版本
如果让你手写，一般可以试着先写一个简易版本的。
【1】底层桶的数量固定，这样的缺点就是后期哈希碰撞的可能性大大增加
【2】元素的键值仅支持int类型
【3】不支持迭代器
【4】不支持动态扩容
【5】仅支持put、get和remove
class Node{
int key, value;
Node prev, next;
Node (int key, int value) {
this.key = key;
this.value = value;
}
}
简易版的节点可以使用以上的定义方式。
private int length = 100;
private Node[] data = new Node[length];
简易版本不支持扩容，桶的固定大小定为100，而且仅使用一个空参构造器
public int get(int key) {
int index = key % length;
Node curr = data[index];
while(curr != null) {
if (curr.key == key) {
return curr.value;
}
curr = curr.next;
}
return -1;
}
计算桶的索引的时候，直接使用取模的方式。并且注意存在哈希冲突的时候，遍历链表。
public void put(int key, int value) {
int index = key % length;
Node curr = data[index];
if (curr == null) {
Node node = new Node(key, value);
data[index] = node;
return;
}
while(true) {
if (curr.key == key) {
curr.value = value;
return;
}
if(curr.next == null) {
Node node = new Node(key, value);
node.prev = curr;
curr.next = node;
return;
} else {
curr = curr.next;
}
}
}
put操作也十分简单，先计算出对应的桶，拿到首节点进行比较（因为使用的是int类型，因此直接进行字面量比较即可）。否则遍历链表，最终的结果无法是某个链表节点的值被覆盖，或是链表尾部插入一个新的节点。
public void remove(int key) {
int index = key % length;
Node curr = data[index];
if (curr != null && curr.key == key) {
Node next = curr.next;
if (next != null) {
next.prev = null;
}
data[index] = next;
return;
}
while(curr != null) {
if (curr.key == key) {
Node next = curr.next;
Node prev = curr.prev;
if (next != null) {
next.prev = prev;
}
if (prev != null) {
prev.next = next;
}
return;
}
curr = curr.next;
}
}
remove方法依然是相似的逻辑：计算桶、判断首元素、遍历链表，最终某个Node节点将被移除
改进版本
上个版本过于简易，可以进行一些改进。
其中阈值字段加不加无所谓了，但是可以参考一下hashMap的默认数据如初始容量16、加载因子0.75等。
class myHashMap<K,V>
可以将类型声明为泛型类。并且将Node节点的类型也加上泛型修饰，此时的Node成员都属于Object类型了，判断的时候也需要作为一个对象去判断。
class MyNode<K,V> {
K k;
V v;
int hash;
MyNode<K,V> next;
}
因为加入泛型后，K和V就相当于成了Object类型，不能再使用等号了而是使用对象的equals方法
key!=null&&key.equals(first.k))
需要注意的是，hashMap源码中Node节点中不但有K和V，而且还要一个int类型的hash成员，我们上面是直接使用key%len得到桶的索引，而现在K不再是int类型了，因此需要使用hash值来计算索引了即node.hash%len。该hash值可以简单地通过hashCode()拿到，或者对hashCode()返回值进行再次哈希计算。
if(first.hash==hash&&(key==first.k||(key!=null&&key.equals(first.k)))){
return first;
}
hashMap中，两个Node节点，只有hash值比较和节点成员Key的equals结果都为false，才会被认为是两个不同的节点。
计算hash值可以直接使用key.hashCode（）方法（hashTable中直接使用hashCode%len计算桶的位置），或者模仿hashMap采用再hash的算法。算法将高低16位相异或进行扰乱计算、
private int hash(K key) {
if(key==null)return 0;
int hashCode=key.hashCode();
int temp=hashCode>>>16;
return hashCode^temp;
}
创建的节点中，hash值就是通过hash(node.key)计算出来的。
void resize(){
MyNode<K,V>[] oldTable =this.table;
int oldCap = (oldTable==null)?0:oldTable.length;
int newCap = oldCap<<1;
MyNode<K,V>[] newTable =(MyNode<K,V>[])new MyNode[newCap];
this.table=newTable;
this.threshold= (int) (this.loadFactor*newCap);
if(oldTable!=null){
for (int i = 0; i < oldTable.length; i++) {
MyNode<K, V> temp = oldTable[i];
while (temp!=null){
int newPos = temp.hash%newCap;
temp.next=newTable[newPos];
newTable[newPos]=temp;
temp=temp.next;
}
}
}
}
扩容的部分可以模仿jdk7的hashMap，因为比较容易懂，但是并发下存在死循环的问题。
迭代器
Iterator接口提供了两个方法next和hashNext，使用迭代器可以使得所有异构的容器具有一个统一的遍历方式，但是如何遍历取决于各个容器的实现。
现在我试着定义一个内部的迭代器类型，并且实现迭代器接口及其对应的方法。
private class MyNodeIterator extends MyHashIterator
implements Iterator<MyNode<K,V>>
实现迭代器，每次迭代返回一个myNode<K, V>类型的对象
MyNode<K,V> next;
MyNode<K,V> cur;
int index;
可以把迭代器想象成一个链表，每迭代一个元素链表就执行一次node=node.next指定next==null为止，因此我们必须使用一些成员保存每一迭代时刻的状态量。
MyNodeIterator(){
MyNode<K, V>[] table = myHashMap.this.table;
this.cur=this.next=null;
this.index=0;
if(table!=null &&myHashMap.this.size>0){
while (index<table.length){
next=table[index++];
if(next!=null)break;
}
}
}
初始化，将迭代器的next指针和cur指针指向第一个不为null的值。如果迭代器一开始读取next就是null，说明整个容器都空的，或者遍历到头了（当然了，具体取决于如何实现，尤其是hasNext方法）。
@Override
public MyNode<K,V> next() {
MyNode<K, V>[] table = myHashMap.this.table;
if(this.next==null) {
System.out.println("元素不存在");
return null;
}
cur=this.next;
this.next=this.next.next;
if(this.next==null&&table!=null){
while (index<table.length){
next=table[index++];
if(next!=null)break;
}
}
return this.cur;
}
@Override
public boolean hasNext(){return next!=null;}
hashMap是没有办法直接使用迭代器的，因此我们还需要在内部创建一个轻量级的Set。使用的时候先通过keySet()或EntrySet()方法拿到这个轻量级的set实例，然后使用对应的iterator方法。
private class MyNodeSet extends AbstractSet<myNode<K,V>> {
@Override
public Iterator<myNode<K, V>> iterator() {
return new MyNodeIterator();
}
}
这个Set仅仅作为一个迭代器视图，本质上还是调用内部创建的迭代器实例。
这里以entry迭代器为例，entrySet()和keySet()没有本质区别，只不过是一个返回的是整个Node节点，另一个返回的是Node节点的key成员。
@Override
public Set<myNode<K,V>> entrySet() {
if(this.entrySet==null)this.entrySet=new MyNodeSet();
return this.entrySet;
}
设计哈希集合
哈希集合的实现和哈希表如出一辙，甚至底层可以直接使用哈希表的代码去实现
力扣地址
这里不基于hashMap而采用原生实现，而且依然提供简易的实现，仅支持int类型的元素。
这里使用一种新的实现方式：数组作为底层数据结构，不使用Node节点，并且使用线性探测法解决哈希冲突
private static final int capacity = 4;
private int cap;
private int size;
private Integer[] keys;
这里提供一个空参和一个指定初始容量的构造器。
public MyHashSet() {
this(capacity);
}
public MyHashSet(int cap) {
this.cap = cap;
size = 0;
keys = new Integer[this.cap];
}
添加元素
public void add(int key) {
if(size >= cap /2) resize(2 * cap);
int i;
for(i = key% cap; keys[i] != null; i = (i + 1) % cap)
{
if(keys[i] == key) return;
}
keys[i] = key;
size++;
}
这里使用线性探测法解决哈希冲突（因为没有使用Node节点，因此无法使用链地址法）
private void resize(int cap) {
MyHashSet temp = new MyHashSet(cap);
for(int i = 0; i < this.cap; i++)
{
if(keys[i] != null){
temp.add(keys[i]);
}
}
keys = temp.keys;
this.cap = temp.cap;
}
注意：这里新建了一个hashSet的对象，并且在这个新的对象中进行添加
这里提供一个扩容方法，扩容策略依然和hashMap一样采用加倍的扩容方式。
这种扩容方式可以实现在一定情况下进行缩容。
public boolean contains(int key) {
for(int i = key% cap; keys[i] != null; i = (i+1) % cap)
{
if(keys[i] == key) return true;
}
return false;
}
此实现的hashSet是基于线性探测解决哈希冲突的，因此整体的元素分布较为紧凑。当一个元素被删除后，后面紧邻的元素很可能是由于为了解决哈希冲突而被放置的，因此需要做一个处理：拿到相邻的元素，删除并重新添加。最终存在两个可能——该元素被放置到了靠左的位置，或者仍然在该位置。
最后可能根据元素数量小于数组的八分之一，可以执行一个缩容操作。
public void remove(int key) {
if(!contains(key)) return;
int i = key% cap;
while(keys[i] != key)
{
i = (i+1) % cap;
}
keys[i] = null;
size--;
i = (i+1) % cap;
while(keys[i] != null)
{
int temp = keys[i];
keys[i] = null;
size--;
add(temp);
i = (i+1) % cap;
}
if(size > 0 && size <= cap /8) resize(cap / 2);
}
|