互联网架构-Java8集合框架源码分析-041：纯手写Jdk7HashMap集合框架

纯手写Jdk7HashMap集合框架

1 HashSet基本使用API介绍

课程主要内容：
1、HashSet底层是如何实现的？
2、HashSet如何确保数据不重复？
3、纯手写Jdk1.7HashMap集合
4、HashMap中Key为null如何存储的？

2 HashSet底层实现原理分析

public class Test001 {
    public static void main(String[] args) {
        HashSet<String> strings = new HashSet();
        strings.add("zhangsan");
        strings.add("lisi");
        strings.add("zhangsan");
        strings.add(null);
        System.out.println(strings.size());
        for (String s : strings) {
            System.out.println(s);
        }
    }
}

运行结果：

HashSet如何保证key值不允许重复？
HashSet底层包装了HashMap，HashMap中key是唯一的，所以HashSet元素值唯一。
HashMap底层如何保证key不允许重复?
hashCode相同且equals比较对象值相等，相同key覆盖旧值。

3 HashMap底层基本实现原理分析

Jdk7 底层实现，链表+数组 Entry封装键值对对象key、value、next
Jdk8 底层实现，链表+数组+红黑树 Node

4 手写简单版本HashMap实现基本功能（put方法）

public interface MayiktMap<K, V> {

    /**
     * 集合大小
     *
     * @return
     */
    int size();

    /**
     * 添加元素
     *
     * @param key
     * @param value
     * @return
     */
    V put(K key, V value);

    /**
     * 根据key查询
     *
     * @param key
     * @return
     */
    V get(K key);

    // 使用Entry对象存放键值对，封装key和value
    interface Entry<K, V> {
        /**
         * 获得key
         * @return
         */
        K getKey();

        /**
         * 获得value
         * @return
         */
        V getValue();

        /**
         * 设置value
         * @param value
         * @return
         */
        V setValue(V value);

    }
}

public class MayiktHashMap<K, V> implements MayiktMap<K, V> {

    // 默认初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    // 加载因子 0.75f 作用：数组扩容
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 最大初始容量 10亿+
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 实际加载因子
    final float loadFactor;

    /**
     * 阈值 需要扩容的时候实际hashMap存放的大小
     * 容量*加载因子 当达到阈值情况下开始扩容
     */
    int threshold;

    //hashMap底层数组 初始为空
    transient Entry<K, V>[] tables = null;

    // 集合大小
    transient int size;

    public MayiktHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MayiktHashMap(int initialCapacity, float loadFactor) {
        // 初始容量校验
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("初始容量不符" + initialCapacity);
        }
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        // 校验加载因子
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("加载因子不符" + loadFactor);
        }
        // 设置加载因子和实际hashMap存放的阈值
        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

    /**
     * 定义空方法便于子类扩展功能
     */
    protected void init() {
    }

    @Override
    public V put(K key, V value) {
        //数组为空，初始化数组
        if (tables == null) {
            inflateTable(threshold);
        }
        // 计算hash值
        int hash = hash(key);
        // 根据hash值计算数组下标存放的位置
        int index = indexFor(hash, tables.length);
        // 判断HashCode相同情况，循环遍历链表
        for (Entry e = tables[index]; e != null; e = e.next) {
            Object k;
            // hashCode相同且值相同情况
            if (e.hash == hash && ((k = e.getKey()) == key || e.getKey().equals(key))) {
                //获取原值value
                Object oldValue = e.getValue();
                //设置新value
                e.setValue(value);
                // 返回原value
                return (V) oldValue;
            }
        }
        // 值不同情况，添加元素
        addEntry(hash, key, value, index);
        return null;
    }

    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);
    }

    private void createEntry(int hash, K key, V value, int bucketIndex) {
        // 获取原来Entry对象，如果获取为空，没有发生hash冲突
        Entry<K, V> next = tables[bucketIndex];
        // 新建一个Entry对象，放在tables对应数组位链表首个位置，如果原来Entry有值，新Entry指向原Entry
        tables[bucketIndex] = new Entry(hash, key, value, next);
    }

    /**
     * 计算hash值
     *
     * @param k
     * @return
     */
    final int hash(Object k) {
        int h = 0;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 根据hash值计算index下标位置
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length - 1);
    }


    /**
     * 默认数组初始化
     *
     * @param toSize
     */
    private void inflateTable(int toSize) {
        int capacity = roundUpToPowerOf2(toSize);
        // 计算初始化容量
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        // 数组中的容量初始化
        tables = new MayiktHashMap.Entry[capacity];
    }

    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

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


    @Override
    public V get(K key) {
        return null;
    }

    class Entry<K, V> implements MayiktMap.Entry<K, V> {
        // key
        private K k;
        // value
        private V v;
        // next 指向下一个Entry
        private Entry<K, V> next;

        // 存放Entry对象的hash值
        private int hash;

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

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

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

        @Override
        public V setValue(V value) {
            this.v = value;
            return this.v;
        }

        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
}

public class Test002 {
    public static void main(String[] args) {
        MayiktHashMap<Object, String> objectStringMayiktHashMap = new MayiktHashMap<>();
        String a = "a";
        Integer b = new Integer(97);
        objectStringMayiktHashMap.put(a, "蚂蚁课堂A");
        objectStringMayiktHashMap.put(b, "蚂蚁课堂B");
    }
}

断点调试：

本文地址：https://blog.csdn.net/u012425860/article/details/112231981