也写个HashMap--HMHashMap

也来写个HashMap;

Map 需要有几个函数,Get/Set/Remove/Size;

其实我们在曾经理解过的Hashmap,为什么会快,有学过二叉树,或者排序的,查找算法的同学可以看看;查询最快的是什么,数组?对,就是数组;

我们来看看Hm 怎么做的?

首先对于我们Map 的数据做两个维度的分类;一个基于hash值的分类,分类在同一类的在同一数组区域;

当然同一数据区域肯定是有同一类属性对吧;

从之前学过的数据看,常用的类似有:取模,平方中位等方法去做;

好有了这个概念就可以做第二步了,定义个Entry接口;

package me.duzhi.demo.hm;

public interface HMMap<K, V> {
    public void put(K k, V v);

    public V get(K k);

    public boolean remove(K k);

    public int size();

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

 

实现一个HMHashmap;

定义一个:

   //** 默认HashTable大小
    private static int defaultLength = 16;
    //** HashTable 大小
    private int length;

    private static double defaultHolder = 0.75;//加载因子
    private double holder;

    private Entry<K, V>[] entries;
    private int entriesLength = 0;
    private int size;

 

这里有个问题了

为什么定义defaultLength为16,delaultHolder为0.75?这个我们等会在讨论;

1、entries 为一个数组;

首先实现两个狗涛函数:

    public HMHashMap(int length, double holder) {
        this.length = length;
        this.holder = holder;
        entries = new Entry[length];
    }

    public HMHashMap() {
        this(defaultLength, defaultHolder);
    }

 

开始来个Put函数;

//根据Kay获取数组的分类;
int index = getIndex(k);
//获取Entry,并且增加entries使用长度
        Entry<K, V> entry = entries[index];
        if (entry == null) {
            entry = newEntry(k, v, null);
            entriesLength++;
        } else {
            entry = newEntry(k, v, entry);
        }
//重新设置entriesp[key]的值
        entries[index] = entry;
//增加map 大小
        size++;

好;之前我们聊过加载因子对吧;

那我们重构出来下;

//设置当length > 长度*因子的时候需要对entries 重新扩展(在扩大entries )
 if (entriesLength > length * holder) {
            resize();
        }
        int index = getIndex(k);
        Entry<K, V> entry = entries[index];
        if (entry == null) {
            entry = newEntry(k, v, null);
            entriesLength++;
        } else {
            entry = newEntry(k, v, entry);
        }
        entries[index] = entry;
        size++;

如何扩展呢?

说白了,三部操作;1、先把原来的数据临时保存一把,2,重新初始化数组,3,把临时数据设置到新数组内。

    private void resize() {
        //临时保存。。我懒,正好定义了Entry 是个单向链表所以直接保存,
        Entry<K, V> cacheEntry = cacheEntry();
        //重新整理
        reEntries();
        put(cacheEntry);
    }
  
  private void reEntries() {
        entries = new Entry[length * 2];
        entriesLength = 0;//初始化数组大小
        length = length * 2; //默认double 
        size = 0;//初始化新的Map 大小
    }

好了,基本也差不多了,从put 到 resize 再到put基本也差不多了;

好;get&remove 就不说了,基本也是按照对链表操作;并且Size需要++等等操作;

OK;

回过头来看看为啥是16&0.75?

 这里h是通过K的hashCode最终计算出来的哈希值,并不是hashCode本身,而是在hashCode之上又经过一层运算的hash值,length是目前容量。这块的处理很有玄机,与容量一定为2的幂环环相扣,当容量一定是2^n时,h & (length - 1) == h % length,它俩是等价不等效的,位运算效率非常高,实际开发中,很多的数值运算以及逻辑判断都可以转换成位运算,但是位运算通常是难以理解的,因为其本身就是给电脑运算的,运算的是二进制,而不是给人类运算的,人类运算的是十进制,这也是位运算在普遍的开发者中间不太流行的原因(门槛太高)。这个等式实际上可以推理出来,2^n转换成二进制就是1+n个0,减1之后就是0+n个1,如16 -> 10000,15 -> 01111,那根据&位运算的规则,都为1(真)时,才为1,那0≤运算后的结果≤15,假设h <= 15,那么运算后的结果就是h本身,h >15,运算后的结果就是最后四位二进制做&运算后的值,最终,就是%运算后的余数,我想,这就是容量必须为2的幂的原因。HashTable中的实现对容量的大小没有规定,最终的bucketIndex是通过取余来运算的。注:我在考虑这样做是否真的是最好,规定容量大小一定为2的幂会浪费许多空间成本,而时间上的优化针对当今越来越牛逼的CPU是否还提升了许多,有些资料上说,CPU处理除法和取余运算是最慢的,这个应该取决于语言调用CPU指令的顺序和CPU底层实现的架构,也是有待验证,可以用Java写段程序测试一下,不过我想,CPU也是通过人来实现,人脑运算的速度应该是加法>减法>乘法>除法>取模(这里指的是正常的算法,不包括速算),CPU也应是如此。
       通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点,可以想想为什么)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子(实际上就是最大条目数小于初始容量*加载因子),则不会发生 rehash 操作。 

 

 

 

 

//Map:

package me.duzhi.demo.hm;

public interface HMMap<K, V> {
    public void put(K k, V v);

    public V get(K k);

    public boolean remove(K k);

    public int size();

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


//


package me.duzhi.demo.hm;

public class HMHashMap<K, V> implements HMMap<K, V> {
    //** 默认HashTable大小
    private static int defaultLength = 16;
    //** HashTable 大小
    private int length;

    private static double defaultHolder = 0.75;//加载因子
    private double holder;

    private Entry<K, V>[] entries;
    private int entriesLength = 0;
    private int size;

    public HMHashMap(int length, double holder) {
        this.length = length;
        this.holder = holder;
        entries = new Entry[length];
    }

    public HMHashMap() {
        this(defaultLength, defaultHolder);
    }

    public void put(K k, V v) {
        if (entriesLength > length * holder) {
            resize();
        }
        int index = getIndex(k);
        Entry<K, V> entry = entries[index];
        if (entry == null) {
            entry = newEntry(k, v, null);
            entriesLength++;
        } else {
            entry = newEntry(k, v, entry);
        }
        entries[index] = entry;
        size++;
    }

    private void resize() {
        //临时保存
        Entry<K, V> cacheEntry = cacheEntry();
        //重新整理
        reEntries();
        put(cacheEntry);
    }

    private void reEntries() {
        entries = new Entry[length * 2];
        entriesLength = 0;
        length = length * 2;
        size = 0;
    }

    private void put(Entry<K, V> cacheEntry) {
        put(cacheEntry.getKey(), cacheEntry.getValue());
        if (cacheEntry.next != null) {
            put(cacheEntry.next);
        }
    }

    private Entry<K, V> cacheEntry() {
        Entry<K, V> cacheEntry = null;//临时存储所有entry;
        for (int i = 0; i < entries.length; i++) {
            Entry<K, V> entry = entries[i];
            if (entry != null) {
                if (cacheEntry == null)
                    cacheEntry = entry;
                else {
                    entryNext(cacheEntry, entry);
                    cacheEntry = entry;
                }
            }
        }
        return cacheEntry;
    }

    private void entryNext(Entry<K, V> cacheEntry, Entry<K, V> entry) {
        if (entry.next == null)
            entry.next = cacheEntry;
        else
            entryNext(cacheEntry, entry.next);
    }

    private Entry<K, V> newEntry(K k, V v, Entry<K, V> entry) {
        Entry entry1 = new Entry<K, V>(k, v);
        entry1.setNext(entry);
        return entry1;
    }

    private int getIndex(K k) {
        int index = k.hashCode() % length;
        return index < 0 ? -index : index;
    }

    public V get(K k) {
        int index = getIndex(k);
        Entry<K, V> entry = entries[index];
        Entry<K, V> currentEntry = getEntryByKey(k, entry);
        return currentEntry == null ? null : currentEntry.getValue();
    }

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

    public boolean remove(K k) {
        int index = getIndex(k);
        if (entries[index] == null) {
            return false;
        } else {
            return replaceEntryByKey(k, entries[index], null);
        }
    }

    private boolean replaceEntryByKey(K k, Entry<K, V> entry, Entry<K, V> lastEntry) {
        if (k == entry.getKey() || k.equals(entry.getKey())) {
            if (lastEntry == null) {
                int index = getIndex(k);
                entries[index] = entry.next;
            } else {
                lastEntry.next = entry.next;
            }
            size--;
            return true;
        } else if (entry.next != null)
            return replaceEntryByKey(k, entry.next, entry);
        return false;
    }

    public int size() {
        return size;
    }

    public static class Entry<K, V> implements HMMap.Entry<K, V> {

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        private K key;
        private V value;
        private Entry<K, V> next;


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

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

        public Entry<K, V> getNext() {
            return next;
        }

        public void setNext(Entry<K, V> next) {
            this.next = next;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

 

代码路径:https://github.com/ashangpeng/IDemo/blob/master/src/main/java/me/duzhi/demo/hm/HMHashMap.java

 

除特别注明外,本站所有文章均为duzhi原创,转载请注明出处来自https://www.duzhi.me/article/12918.html

联系我们

******

在线咨询:点击这里给我发消息

邮件:ashang.peng#aliyun.com

QR code