HashMap学习--手动写一个简单的HashMap进行理解
1.结点Node的定义
public class Node {
public int hash;
public Object key;
public Object value;
public Node next;
}
HashMap的基础时一个数组，数组里每个元素是一个node，他必须包括:hash值，key键值，value，next下一个结点，同一个hash值的结点用一条链栓起来。
2.HashMap的定义
Node[] table;//核心数组
int size;//元素个数
public HashmapTest(){
table=new Node[16];//初始化数组大小，尽量2的整数幂
size=0;
}
这个数组大小有讲究，从两个极端理解，当大小为1时，也就是所有的元素栓在一个位子上，也就是退化成了链表。如果数组很大，也就是元素所有元素几乎可以散在数组的每个位子上，也就是退化成了数组。至于取2的整数幂，可以将取余的操作使用按位&，加快速度，除法在计算机中的速度是很慢的。
3.HashMap的增删改查
增加一个元素
public void put(K key,V value){
Node newNode=new Node();
Node lastNode=null;
Boolean isRepeat=false;
newNode.hash=myhash(key.hashCode(),table.length);//简单的计算hash值的函数，就是对数组大小进行取余，不考虑扩容以及优化
newNode.key=key;
newNode.value=value;
newNode.next=null;
if(table[newNode.hash]==null){
table[newNode.hash]=newNode;
}else{
Node tmp=table[newNode.hash];
while (tmp!=null){
if(tmp.key.equals(key)){
isRepeat=true;
tmp.value=value;
break;
}else{
lastNode=tmp;
tmp=tmp.next;
}
}
if(isRepeat==false){
lastNode.next=newNode;
}
}
}
删除对应key值的元素
public void delete(K key){
int hash=myhash(key.hashCode(),table.length);
Node temp=table[hash];
Node prevNode=null;//记住前一个结点，删除时要接上。
while(temp!=null){
//第一个结点的特殊操作
if(temp.key.equals(table[hash].key)){
//第一个对上了
if(temp.key.equals(key)){
table[hash]=temp.next;
break;
}else{
prevNode=temp;
temp=temp.next;
}
}else{
if(temp.key.equals(key)){
prevNode.next=temp.next;
break;
}else{
temp=temp.next;
}
}
}
}
修改一个元素
public void set(K key,V value){
Node temp=table[myhash(key.hashCode(),table.length)];
while (temp!=null){
if(temp.key.equals(key)){
temp.value=value;
break;
}else {
temp=temp.next;
}
}
}
查找一个元素
public V get(K key){
int hash=myhash(key.hashCode(),table.length);
Node tmp=table[hash];
if(tmp==null){
return null;
}else{
while (tmp!=null){
if(tmp.key.equals(key)){
return (V)tmp.value;
}else {
tmp=tmp.next;
}
}
return null;
}
}
转载于:https://www.cnblogs.com/CszShuzi/p/11056838.html
