HashMap 原理

1. 以键值对（key-value）的形式存储元素
2. 通过 hashcode() 和 equals() 方法定位键值对存储的准确位置
   1. 首先通过 hashcode() 获得key映射的散列值（也叫 hash 值），通过 hash 值确定键值对存储在哪个链表。不过，不同的 key 生成的 hash 值可能是一样的。
   2. 如果 hash 值定位到的存储空间存在其它的键值对，那就通过 equals() 比较 key ，如果一样，就更新它的 value，如果不一样，就添加在链表后面
   3. 通俗的说，hashcode() 就相当于字典目录，确定好某个字所在的页数，equals()相当于页数上存放的位置
3. 在场景应用上，hashcode() 和 equals() 是重点修改的部分

来自 how2j.cn

手动实现 HashMap

// 键值对存储
package HashMap;

public class Entry {
    
    public Object key;
    public Object value;
    
    public Entry(Object key, Object value){
        this.key = key;
        this.value = value;
    }
    
    @Override
    public String toString() {
        return "[key=" + key + ", value=" + value + "]";
    }
}

// put，get接口
package HashMap;

public interface IHashMap {
    public void put(Object key, Object object);
    public Object get(Object key);
}

package HashMap;

import java.util.LinkedList;

public class MyHashMap implements IHashMap {

    LinkedList<Entry>[] values = new LinkedList[2000];

    @Override
    public void put(Object key, Object value) {
        // 获得 hash 值
        int hashcode = hashcode(key);
        // 根据 hash 值确定存储在哪个链表位置
        LinkedList<Entry> list = values[hashcode];
        if (null == list) {
            list = new LinkedList<>();
            values[hashcode] = list;
        }
        boolean found = false;
        for (Entry entry : list) {
            // 通过比较确定存储的链表位置
            if (key.equals(entry.key)) {
                entry.value = value;
                found = true;
                break;
            }
        }
        if (!found) {
            Entry entry = new Entry(key, value);
            list.add(entry);
        }
    }

    @Override
    public Object get(Object key) {
        // 获得 hash 值
        int hashcode = hashcode(key);
        // 根据 hash 值确定存储在哪个链表位置
        LinkedList<Entry> list = values[hashcode];
        if (null == list)
            return null;
        Object result = null;
         // 通过比较确定存储的链表位置，并取出相应的 value
        for (Entry entry : list) {
            if (entry.key.equals(key)) {
                result = entry.value;
            }
        }
        return result;
    }
    
    // 自定义 hash 值，使其落在 0~1999 之间
    private int hashcode(Object obj) {
        String str = obj.toString();
        if (0 == str.length())
            return 0;

        int hashcode = 0;
        char[] cs = str.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            hashcode += cs[i];
        }
        hashcode *= 23;
        // 取绝对值
        Math.abs(hashcode);
        // 取值落在 0 - 1999 之间
        hashcode %= 2000;
        return hashcode;
    }
    
    public static void main(String[] args) {
        MyHashMap map =new MyHashMap();

        map.put("test", "坦克");
        map.put("test", "物理");
        map.put("t", "坦克2");
        System.out.println(map.get("test"));
        

   }

}

运行结果

场景应用

1. 有一个 people 类，HashMap 的 key 想通过 name 和 age 判断 people 是否相等，而不是通过 people 对象的存储地址

实现方法：根据 HashMap 原理，需同时重写 equals() 和 hashCode()。很容易犯的错误是，只重写 equals()，而忘记重写 hashCode()

package HashMap;

import java.util.HashMap;
import java.util.Set;

class People {
    private String name;
    private int age;

    public People(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int hashCode() {
        return name.hashCode() * 37 + age;
    }

    @Override
    public boolean equals(Object obj) {
        return this.name.equals(((People) obj).name) && this.age == ((People) obj).age;
    }

    public static void main(String[] args) {
        People p1 = new People("Jack", 12);
        HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
        hashMap.put(p1, 1);

        System.out.println(hashMap.get(new People("Jack", 12)));
    }
}

运行结果

代码存放

https://github.com/RiveLock/test/tree/master/src/HashMap

参考

http://how2j.cn/k/collection/collection-hashcode/371.html#nowhere

https://www.cnblogs.com/dolphin0520/p/3681042.html