博客

学习hashmap源码，写一下数组加链表的实现方式。

定义一个Map接口

package map;

public interface Map<K, V> {
    V put(K k, V v);
    V get(K k);
    int size();

    interface Entry<K, V>{
        K getKey();
        V getValue();
    }

}

Map的实现类

package map;

public class HashMap<K ,V> implements Map<K, V> {
    Entry<K, V> table[] = null;
    int size = 0;
    int capacity = 8;

    public HashMap(){
        // 初始化Entry数组
        table = new Entry[capacity];
    }

    /**
     * 首先计算key的hashcode，根据hashcode从数组里面取值
     * 如果取出的是空，说明当前数组对应的下标是空的，可以写数据
     * 反之，说明对应的下标有值(发生hash碰撞)，此时使用链表存储在数据对应的下标
     * **/
    @Override
    public V put(K k, V v) {
        int index = hash(k);
        System.out.println("key hash code: "+index);
        Entry<K, V> entry = table[index];
        if(entry == null){
            table[index] = new Entry(k, v, index, null);

        }else {
            // 如果数组下标对应的位置被占了，
            table[index] = new Entry(k, v, index, entry);
        }
        size ++;
        return v;
    }

    @Override
    public V get(K k) {
        if(k == null){
            return null;
        }
        int index = hash(k);
        Entry<K, V> entry = table[index];
        return find(k, entry);
    }

    /**
     * 递归从链表取值
     * **/
    private V find(K k, Entry<K, V> entry){
        if (k == entry.getKey() || k.equals(entry.getKey())){
            return entry.getValue();
        }else {
            if(entry.next != null){
                return find(k, entry.next);
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 计算key的hash值，比较取余和位运算两种方式，结果需要一致
     * **/
    int hash(K k){
        int i = k.hashCode() & (capacity-1);
//        int i = k.hashCode() % capacity-1;
        return Math.abs(i);
    }

    /**
     * 内部类，链表
     * **/
    class Entry<K, V> implements Map.Entry<K, V>{

        K k;
        V v;
        int hash;
        Entry<K, V> next;

        public Entry(K k, V v, int hash, Entry<K, V> next){
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }

}

        Map<String, Object> map = new HashMap<>();
        map.put("5", "jaklsdj");
        map.put("16", "jalsjdf");
        System.out.println(map);
        System.out.println(map.get("5"));
        System.out.println(map.get("16"));
        System.out.println(map.size());

key hash code: 5
key hash code: 5
map.HashMap@2626b418
jaklsdj
jalsjdf
2