【深究系列】实现自己的HashMap

【深究系列】实现自己的HashMap

【深究系列】实现自己的HashMap

public class MyHashMap {
    static class Entry{
        private Object key;
        private Object value;
        private Entry next;
        public Entry(Object key, Object value) {
            this.key = key;
            this.value = value;
        }
        public Object getKey() {
            return key;
        }

        public void setKey(Object key) {
            this.key = key;
        }

        public Object getValue() {
            return value;
        }

        public void setValue(Object value) {
            this.value = value;
        }

        public Entry getNext() {
            return next;
        }

        public void setNext(Entry next) {
            this.next = next;
        }
    }

    private Entry[] table;
    private int capacity = 16;
    private float loadfactor = 0.75f;
    private int size = 0;

    public MyHashMap() {
        table = new Entry[capacity];
    }

    public void put (Object key, Object value) {
        int index = key.hashCode() % capacity;
        Entry entry = new Entry(key, value);
        //头结点
        Entry head = table[index];
        if (head == null){
            table[index] = entry;
            size++;
        }
        else {//发生hash冲突,查看是更新还是重新赋值
            for (Entry e = head; e != null; e = e.getNext()) {
                //对于每一个entry,先判断是不是要覆盖
                if ((e.getKey().hashCode() == key.hashCode()) && (e.getKey() == key || e.getKey().equals(key))) {
                    e.value = value;
                    break;
                } else {
                    if (e.next == null) {
                        //当前e是最后一个节点
                        entry.next = head;
                        table[index] = entry;
                        size++;
                    }
                }
            }
            if (size > capacity * loadfactor) {
                resize(capacity << 1);
            }
        }
    }

    private void resize(int newCapacity) {
        System.out.println("-----------------扩容了-----------------");
        Entry[] newTable = new Entry[newCapacity];
        Entry[] src = table;
        for (int i = 0; i < src.length; i++) {
            Entry head = src[i];
            if (head != null) {
                Entry e = head;
                do {
                    Entry nextEntry = head.next;
                    int index = e.getKey().hashCode() % newCapacity;
                    e.next = newTable[index];
                    newTable[index] = e;

                    e = nextEntry;
                } while(e != null);
            }
        }
        table = newTable;
        capacity = newCapacity;
    }

    public Object get(Object key) {
        if (key == null) return null;
        int index = key.hashCode() % capacity;
        Entry head = table[index];
        for (Entry e = head; e != null; e = e.next) {
            if (e.key.equals(key) || e.key == key)
                return e.getValue();
        }
        return null;
    }

    public void remove(Object key) {
        if (key == null) return;
        int index = key.hashCode() % capacity;
        Entry pre = null;
        Entry cur = table[index];
        while (cur != null) {
            if (cur.getKey().hashCode() == key.hashCode() && (cur.getKey() == key || cur.getKey().equals(key))) {
                if (pre == null)
                    table[index] = cur.next;
                else
                    pre.next = cur.next;
                size--;
                return;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    public void print() {
        for (int i = 0; i < table.length; i++) {
            System.out.print("下标[" + i + "] ");
            for (Entry e = table[i]; e != null; e = e.next) {
                System.out.print("【key = " + e.key + ",value = " + e.value + "】 ");
            }
            System.out.println();
        }
    }
}
上一篇:28 API07 ——注解、定义注解


下一篇:聚合搜索