如何从零用Java构建一个简单HashMap

setHashCode(K key)方法里:通过key计算散列值

set(K key, V value)方法里:我们需要使用setHashCode(K key)的方法去计算hash值,然后取模16,之后用这个值integer,获取对应数组entrys下标所对应的Entry,然后entrys[integer]判断是否为空,如果是空的话,给这个entrys[integer]赋值,如果不是空的话,遍历entry到最后一个节点,加进去.

get(K key)方法里:我们需要使用setHashCode(K key)的方法去计算hash值,然后取模16,之后用这个值integer,获取对应数组entrys下标所对应的Entry,然后遍历这个Entry,如果这个Entry的key和我们输入的key相同,返回new Entry(),如果不相同,继续遍历

public class ConstructHashMap {

    public static final int DEFAULT_INITIAL_CAPACITY = 16;

    public static Entry[] entries = new Entry[DEFAULT_INITIAL_CAPACITY];

    static class Entry {
        private int hash;
        private K key;
        private V value;
        private Entry next;

        public Entry() {

        }

        public Entry(Entry entry) {
            this.hash = entry.hash;
            this.key = entry.key;
            this.value = entry.value;
        }

        public Entry(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }

        public void set(K key, V value) {
            int hash = setHashCode(key);
            Integer integer = hash % 16;
            Entry entry = entries[integer];
            if (entry == null) {
                entries[integer] = new Entry(hash, key, value);
                return;
            }

            while (entry.next != null) {
                entry = entry.next;
            }
            entry.next = new Entry(hash, key, value);
        }

        private Entry get(K key) {
            int hash = setHashCode(key);
            Integer integer = hash % 16;
            Entry entry = entries[integer];
            while (entry != null) {
                if (entry.key == key) {
                    return new Entry(entry);
                }
                entry = entry.next;
            }
            return null;
        }

        private Integer setHashCode(K key) {
            int h;
            //为了更好的均匀散列表的下标
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

        @Override
        public String toString() {
            return "key=" + key +
                    ", value=" + value;
        }
    }


    public static void main(String[] args) {

        for (int i = 0; i < 6; i++) {
            Entry entry = new Entry<>();
            entry.set(i, "第" + i + "个表");
        }

        Entry entry = new Entry<>();
        for (int i = 0; i < 6; i++) {
            System.out.println(entry.get(i));
        }
    }
}