手撕HashMap

前言：

平时工作的时候，用的最多的就是ArrayList和HashMap了，今天看了遍HashMap的源码，决定自己手写一遍HashMap。

一、创建MyHashMap接口

我们首先创建一个MyHashMap的入口，暴露一个外部调用的接口，里面简单的定义一下put和get。

public interface MyHashMap<K,V> {

    public V put(K k,V v);

    public V get(K k);

    interface Entry<K,V>{

        public K getKey();

        public V getValue();

    }

}

二、建一个实现类MyHashMapImpl

接口定义完成之后，那就要开始实现了，我们首先创建一个类MyHashMapImpl来实现MyHashMap。然后我们定义一些变量。以及构造函数，比如我们定义的数组初始长度为16，加载因子为0.75。这两个参数会涉及到自动扩容，我们后面再说。

public class MyHashMapImpl<K, V> implements MyHashMap<K, V> {

//数组的初始长度
private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//阀值比例(加载因子)
private static final float DEFAULT_LOAD_FACTOR = 0.75f;

private int defaultInitSize;

private final float defaultLoadFactor;

//Map当中entry的数量
private int entryUseSize;

//数组
private Entry<K, V>[] table;

//构造函数
public MyHashMapImpl() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public MyHashMapImpl(int defaultInitialCapacity, float defaultLoadFactor) {

    if (defaultInitialCapacity < 0)
        //容量不合规
        throw new IllegalArgumentException("Illegal initial capacity" + defaultInitialCapacity);
    if (defaultLoadFactor <= 0 || Float.isNaN(defaultLoadFactor))
        //不合规的加载因子
        throw new IllegalArgumentException("Illegal load factor" + defaultLoadFactor);
    this.defaultInitSize = defaultInitialCapacity;
    this.defaultLoadFactor = defaultLoadFactor;
    table = new Entry[this.defaultInitSize];
}

}

三、重写put方法

我们首先重写下put方法，可以看到，当Map中存储的数据大于加载因子*初始化数据长度的时候，会第一时间触发扩容机制，扩容的过程也就是重新设置一个更大的数组，并把原本的数组地址指过去，并且把原本的值重新put进去。这个过程如果频繁发生还是很消耗机器性能的，所以我们在写代码的时候最好是预估好初始大小，尽量不触发扩容机制。

 @Override

    public V put(K k, V v) {

        V oldValue;

        //是否需要扩容

        //扩容完毕，肯定需要重新散列

        if (entryUseSize >= defaultInitSize * defaultLoadFactor) {

            resize(2 * defaultInitSize);

        }

        int index = hash(k) & (defaultInitSize - 1);

        if (table[index] == null) {

            table[index] = new Entry<K, V>(k, v, null);

            ++entryUseSize;

        } else {

            Entry<K, V> entry = table[index];

            Entry<K, V> e = entry;

            while (e != null) {

                if (k == e.getKey() || k.equals(e.getKey())) {

                    oldValue = e.value;

                    e.value = v;

                    return oldValue;

                }

                e = e.next;

            }

            table[index] = new Entry<K, V>(k, v, entry);

            ++entryUseSize;

        }

        return null;

    }

 private void resize(int i) {

        Entry[] newTable = new Entry[i];

        defaultInitSize = i;

        entryUseSize = 0;

        rehash(newTable);

    }

private void rehash(Entry<K, V>[] newTable) {

        //得到原来老得entry集合，注意遍历单链表

        List<Entry<K, V>> entryList = new ArrayList<Entry<K, V>>();

        for (Entry<K, V> entry : table) {

            if (entry != null) {

                do {

                    entryList.add(entry);

                    entry = entry.next;

                } while (entry != null);

            }

        }

        //覆盖旧的引用

        if (newTable.length > 0) {

            table = newTable;

        }

        //重新hash也就是重新put entry到hashmap

        for (Entry<K, V> entry : entryList) {

            put(entry.getKey(), entry.getValue());

        }

    }

  class Entry<K, V> implements MyHashMap.Entry<K, V> {

        private K key;

        private V value;

        private Entry<K, V> next;

        public Entry() {

        }

        public Entry(K key, V value, Entry<K, V> next) {

            this.key = key;

            this.value = value;

            this.next = next;

        }

        @Override

        public K getKey() {

            return key;

        }

        @Override

        public V getValue() {

            return value;

        }

    }

四、重写get方法

如果要拿到数组中的值，我们首先要获取对应的位置。其中有一个基本概念要说一下，每一个数据通过hash函数都会得到一个值，并且这个值是固定的，所以我们可以通过k.hashCode()

来获取对应的hash值，然后按照散列算法均匀分散hash值，然后通过hashcode获取对应的值，得到基本数组的下标。这时候就能拿到我们存在map中的值了，但是hash值并不是一定是唯一的，也就是说可以能a.hash和b.hash值是一样的，但是a不等于b，所以如果两个数据hash值相同，会触发hash冲突。严重降低hashmap的性能，本次hash方法的作用也就是尽量减少hash冲突。使数据排列的更加均匀一些。当我们遇到hash冲突的时候可以再次hash解决冲突。

  @Override

    public V get(K k) {

        int index = hash(k) & (defaultInitSize - 1);

        if (table[index] == null) {

            return null;

        } else {

            Entry<K, V> entry = table[index];

            do {

                if (k == entry.getKey() || k.equals(entry.getKey())) {

                    return entry.value;

                }

                entry = entry.next;

            } while (entry != null);

        }

        return null;

    }

巴特西

手撕HashMap

最新文章

热门文章