在Java的库文件里定义了不少哈希表结构的类，如HashMap, HashLinkedMap, HashSet等，但个人还是觉得不管是什么数据结构，都很有必要自己写一下实现类和几个主要的方法比较便于深度理解这种结构和其对应方法，以及时间复杂度等，这样你再直接用比如Java自带的库文件定义的类的时候就会运用自如吧。我们主要实现链式存储Hash Table的以下几种方法：
-get(k key):根据key获取value
-getSize():获取hash
table的大小
-add():添加新的元素到hash
table,添加元素的时候考虑两种情况，第一种是检查是否已经存在一样的key了，如果存在，则更新value 即可，如果不存在则重新添加新的节点，同时添加元素要考虑填充因子的大小，官方叫负载因子（load factor），如果大于0.7了就要扩充链表的大小了，并重新把所有节点复制到新的表里。
-remove():删除key,value对
-isEmpty():hash table是否为空
package zexin;
import java.util.*;
public class HashMapByJava <K,V>{
class Node<K,V>{
K key;
V value;
Node<
K,V> next;
public Node(K key,V value){
this.key = key;
this.value = value;
}
}
private ArrayList<Node<K,V>> hashNodeArraylist;
//the max size of the array list
private int numNode;
// the size of thearray list
private int size;
public HashMapByJava(){
hashNodeArraylist = newArrayList<>();
//it's better to set the initial max length of thecontainer to a
//zhishu
numNode = 11;
size=0;
for(int i = 0;i<numNode;i++)
hashNodeArraylist.add(null);
}
public int size(){
return size;
}
public boolean isEmpty(){
return size()==0;
}
//get the index for storing the node in the arraylist:
private int getIndex(K key){
int hashCode= key.hashCode();
int nodeIndex
= hashCode % numNode;
return nodeIndex;
}
//remove from a give key
public V remove (K key){
int nodeIndex= getIndex(key);
Node<
K,V> head = hashNodeArraylist.get(nodeIndex);
Node<
K,V> prev = null;
while(head
!= null){
if(head.key.equals(key))
break;
prev = head;
head = head.
next;
}
if(head == null)
return null;
size --;
if(prev
!= null)
prev.
next = head.next;
else
hashNodeArraylist.set(nodeIndex,head.next);
return head.value;
}
//get the value from a key
public V get(K key){
int nodeIndex= getIndex(key);
Node<
K,V> head = hashNodeArraylist.get(nodeIndex);
while (head
!= null){
if(head.key.equals(key))
return head.value;
head = head.
next;
}
//if key not found:
return null;
}
//add method base on a key value pair
public void add(K key, V value){
int nodeIndex= getIndex(key);
Node<
K,V> head = hashNodeArraylist.get(nodeIndex);
//cheak if there's already a key that present in thechain
while(head
!= null){
if(head.key.equals(key)){
head.
value = value;
return;
}
head = head.
next;
}
size++;
head =
hashNodeArraylist.get(nodeIndex);
Node<
K,V> newNode = new Node<K,V>(key,value);
newNode.
next = head;
hashNodeArraylist.set(nodeIndex,newNode);
//if the load factor larger than 0.7 or 0.8, double thehash talbe size
if((size * 1.0)/numNode >=0.7 ){
ArrayList
K,V>> temp = hashNodeArraylist;
hashNodeArraylist = newArrayList<>();
numNode = 2*numNode;
size =0;
for(int i = 0; i< numNode;i++)
hashNodeArraylist.add(null);
for(var headNode : temp){
while (headNode != null){
add(headNode.
key,headNode.value);
headNode = headNode.
next;
}
}
}
}
}
网友评论