Java之HashMap的底层实现

摘要

本博客主要讲述了Java的HashMap的底层实现

HashMap的底层原理

底层原理：数组+链表


过程总结：每一个Object的有一个哈希值，通过hashCode()函数获取哈希值，再通过自定义的hash()函数，得到一个值，也就是数组的下标。数组中的每个元素都是一个链表或为空。

哈希值转换为数组下标

//这就是hash函数，val就是key的哈希值，即val = key.hashCode()
//length 必须是2的整数幂
private int  hash(int val, int length){
       return val & (length - 1);
   }

节点

定义链表中的节点

public class Node2 {
    int hash;//hash对应数组下标
    Object key;
    Object value;
    Node2 next;
}

初始化

//数组元素的类型为Node2
Node2[] table;
int size;

public SxtHashMap02() {
    table = new Node2[16];
}

put(Object key, Object value)

public void put(Object key, Object value){
        Node2 newNode = new Node2();
        newNode.hash = hash(key.hashCode(),table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;

        Node2 last = null;//这个学习一下，记录最后一个节点
        int index = hash(key.hashCode(),table.length);
        if(table[index] == null){
            table[index] = newNode;
            size ++;
        }else{
            Node2 tmp = table[index];
            while(tmp != null){
                if(key.equals(tmp.key)){
                    System.out.println("key重复了");
                    tmp.value = value;
                    return;
                }else {
                    last = tmp;
                    tmp = tmp.next;
                }
            }
            last.next = newNode;
            size ++;//size的增加与减少不要忘记
        }
    }

重写toString()

public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i = 0; i < table.length; i ++){
            Node2 temp = table[i];
            while(temp != null){
                sb.append(temp.key + ":" + temp.value + ",");
                temp = temp.next;
            }
        }
        //这个套路学一下，将最后改为']'
        sb.setCharAt(sb.length() - 1,']');
        return sb.toString();
}	

这个toString()有什么用呢？在使用system.out.println()打印的时候，就会用到toString()。

get(Object key)

//根据Map的底层原理，就十分简单
public Object get(Object key){
        int hashCode = key.hashCode();
        int hash = hash(hashCode,table.length);
        Node2 temp = table[hash];
        while(temp != null){
            if(temp.key.equals(key)) return temp.value;
            temp = temp.next;
        }
        return null;
}

增加泛化

public class Node3<K,V> {
    int hash;
    K key;
    V value;
    Node3 next;
}

public class SxtHashMap03<K,V> {
    Node3[] table;
    int size;

    public SxtHashMap03() {
        table = new Node3[16];
    }

    public V get(K key){
        int hashCode = key.hashCode();
        int hash = hash(hashCode,table.length);
        V value = null;
        Node3 temp = table[hash];
        while(temp != null){
            if(temp.key.equals(key)){
                value = (V)temp.value;
            }
            temp = temp.next;
        }
        return value;
    }
    public void put(K key, V value){
        Node3 newNode = new Node3();
        newNode.hash = hash(key.hashCode(),table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;

        Node3 last = null;
        int index = hash(key.hashCode(),table.length);
        if(table[index] == null){
            table[index] = newNode;
            size ++;
        }else{
            Node3 tmp = table[index];
            while(tmp != null){
                if(key.equals(tmp.key)){
                    System.out.println("key重复了");
                    tmp.value = value;
                    return;
                }else {
                    last = tmp;
                    tmp = tmp.next;
                }
            }
            last.next = newNode;
            size ++;
        }
    }
}

remove(K key)

 public void remove(K key){
        int index = hash(key.hashCode(), table.length);
        Node3 temp = table[index];
        if(temp == null) return;
        if(temp.key.equals(key)){
            table[index] = temp.next;
            size --;
            return;
        }
        Node3 last = null;
        while(temp != null){
            if(temp.key.equals(key)){
                last.next = temp.next;
                size --;
                return;
            }
            last = temp;
            temp = temp.next;
        }
}

参考: 手工实现HashMap