基于JDK1.7写自己的HashMap--2020-11-21

一直对jdk的map内部结构很是困惑,鼓起勇气啃了源码,自己写了一个简单版本map,希望对java小萌新有点帮助。

源码

/**带有自动扩容能力**/
public class myHashMapPlus<K, V> implements Map<K, V> {

    volatile int size = 0;
    private Entry<K, V>[] table;
    private static int DEFAULT_INITIAL_CAPACITY = 16;
    private int MAXIMUM_CAPACITY = Integer.MAX_VALUE;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private float loadFactor;
    /**size>ExpansiontThreshold扩容【ExpansiontThreshold=capacity*2*DEFAULT_LOAD_FACTOR】**/
    private int expansiontThreshold;
    /**数组长度,size>ExpansiontThreshold扩容[capacity=capacity*2]**/
    private int capacity;

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

    public myHashMapPlus(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public myHashMapPlus(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        }

        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }

        if(initialCapacity<DEFAULT_INITIAL_CAPACITY){
            initialCapacity=DEFAULT_INITIAL_CAPACITY;
        }

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }

        this.loadFactor = loadFactor;
        this.expansiontThreshold = (int) (initialCapacity * this.loadFactor);
        this.capacity = initialCapacity;
        this.table = new Entry[capacity];
    }

    /**
     * 通过key进行hash
     * hash和数组长度得到index数组下标
     * 判断为空:直接存储
     * 判读不为空:冲突--用链表解决
     * 返回数据
     *
     * @param k
     * @param v
     * @return
     */
    public V put(K k, V v) {
        if (k == null) {
            throw new IllegalArgumentException("key should not null");
        }
        /**确保容量可用,不可用扩容**/
        ensureCapacityInternal(size + 1);

        int index = hash(k);
        Entry<K, V> entry = table[index];
        Entry<K, V> bakEntry =entry;
        if (entry == null) {
            table[index] = new Entry<K, V>(k, v, k.hashCode(), null);
            size++;
            return v;
        }
        /**头插法**/
        while (entry != null) {
            /**已经存在相同的key**/
            if(entry.k.equals(k)){
                entry.v=v;
                return v;
            }
            entry=entry.next;
        }
        /**不存在不相同的key**/
        table[index] = new Entry<K, V>(k, v, k.hashCode(), bakEntry);

        size++;
        return v;
    }

//  /**
//   * 扩容重新计算存入新的table的时候用
//   *
//   * @param k
//   * @param v
//   * @param newTable
//   * @return
//   */
//  public V put(K k, V v,Entry[] newTable) {
//      if (k == null) {
//          throw new IllegalArgumentException("key should not null");
//      }
//      int index = hash(k);
//      Entry<K, V> entry = newTable[index];
//      if (entry == null) {
//          newTable[index] = new Entry<K, V>(k, v, k.hashCode(), null);
//      } else {
//          //头插法
//          newTable[index] = new Entry<K, V>(k, v, k.hashCode(), entry);
//      }
//      size++;
//      return v;
//  }
    private void ensureCapacityInternal(int miniCapacity) {
        if (miniCapacity > expansiontThreshold) {
            /**扩容**/
            grow(miniCapacity);
        }
    }

    /**
     * 扩容数组
     *
     * @param miniCapacity
     */
    private void grow(int miniCapacity) {
        System.out.println("grow table----------------");
        if (miniCapacity > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("capacity is max, cannot put " +
                    "any element");
        }
        int newCapacity = capacity * 2;
        if (newCapacity > Integer.MAX_VALUE) {
            newCapacity = Integer.MAX_VALUE;
        }

        this.capacity = newCapacity;
        this.expansiontThreshold = (int) (capacity * loadFactor);

        Entry[] newTable = new Entry[newCapacity];
        /**扩容后,需要将原来table中所有的值,重新计算存入新的table**/
        ReHashOriginalValue(newTable);

        this.table = newTable;

    }

    /**
     * Transfers all entries from current table to newTable.
     *
     * @param newTable
     */
    private void ReHashOriginalValue(Entry[] newTable) {
        System.out.println("Transfers all entries from current table to newTable.");
        for (Entry<K, V> e : table) {
            while (null != e) {
                Entry<K, V> next = e.next;
                int index = hash(e.getKey());
                e.next = newTable[index];
                newTable[index] = e;
                e = next;
            }
        }
    }


    /**
     * key的hashcode和数组长度取模
     *
     * @param k
     * @return
     */
    private int hash(K k) {
        int hash = k.hashCode() % this.capacity;
        return Math.abs(hash);
    }

    /**
     * 1.通过key进行hashcode计算index
     * 2.index下表数组查询得到Entry
     * 3.Entry==null,没有找到value
     * 4.Entry!=null。判断得到的hashcode是否相等
     * 5.hashcode不相等,判断是否有next,next为空返回null,不存在值
     * 6.hashcode不相等,判断是否有next,next不为空,用下一个重复5.6.7动作
     * 7.hashcode相等,返回值
     *
     * @param k
     * @return
     */
    public V get(K k) {
        if (size == 0) {
            return null;
        } else {
            int index = hash(k);
            Entry<K, V> entry = findValue(k, table[index]);
            if (entry != null) {
                return entry.getValue();
            }
        }
        return null;
    }

    private Entry<K, V> findValue(K k, Entry<K, V> kvEntry) {
        if (kvEntry == null) {
            return null;
        }
        if (k.equals(kvEntry.getKey())) {
            return kvEntry;
        } else {
            if (kvEntry.next != null) {
                return findValue(k, kvEntry.next);
            }
        }
        return null;
    }

    public int size() {
        return this.size;
    }

    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;
        }

        public K getKey() {
            return k;
        }

        public V getValue() {
            return v;
        }

    }
}

简单测试--测试是否自动扩容

public class myHashMapPlusTest {
    public static void main(String[] args) {
        myHashMapPlus map = new myHashMapPlus();
        for (int i = 0; i < 1024; i++) {
            map.put(i, i);
        }
        for (int i = 0; i < 1024; i++) {
            System.out.println(map.get(i));
        }
    }
}

自动扩容测试结果

image.png

扩容条件

数组长度size>ExpansiontThreshold需要扩容,扩容后数组的新容量为:capacity=capacity*2

扩容后的下次再扩容阈值为

ExpansiontThreshold=2*(capacity * DEFAULT_LOAD_FACTOR)
说明:jdk中DEFAULT_LOAD_FACTOR默认为0.75,这里沿用即可

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,386评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,142评论 3 394
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,704评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,702评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,716评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,573评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,314评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,230评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,680评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,873评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,991评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,706评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,329评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,910评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,038评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,158评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,941评论 2 355

推荐阅读更多精彩内容

  • 一、先来复习一下我们常用的几个方法 二、HashMap类图结构 三、HashMap数据结构 我们知道在Java中最...
    无量散人阅读 748评论 0 2
  • 目录 一.简介 二.数据结构 三.具体使用 四.基础知识 五.源码分析 六.源码总结 七.与jdk1.8的区别 八...
    tyangx阅读 161评论 0 0
  • 在看关于HashMap 1.7 BUG时,即多线程时会导致死锁。从而去查找相关资料,看看到底是什么原因造成的。 总...
    阡陌笙箫阅读 139评论 0 0
  • 1 概述本文将从几个常用方法下手,来阅读HashMap的源码。按照从构造方法->常用API(增、删、改、查)的顺序...
    小小的coder阅读 180评论 0 0
  • 久违的晴天,家长会。 家长大会开好到教室时,离放学已经没多少时间了。班主任说已经安排了三个家长分享经验。 放学铃声...
    飘雪儿5阅读 7,523评论 16 22