JAVA整理06---手写简单的HashMap来学习hashmap

男娘i 2021-12-13 13:51 217阅读 0赞

# 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