Android HashMap

参考
参考
参考Yikun
参考Java7 HashMap分析
参考CSDN

HashMap是一个散列链表,它由数组作为容器,每一个元素是一个链表。在创建HashMap的时候会根据默认的临界域创建一个长度是n的2次方的数组,因为元素的位置由hash和lenght共同决定
当length是n^2时,可以更好的减少碰撞。在插入元素时首先会遍历容器是否有相同的元素。如果有会覆盖之前的元素。如果没有在当前位置链表头结点放置新的元素,如果原先的位置有元素,那么新元素指向老的元素形成链表。在查找元素的时候会遍历数组中的每一个链表以及链表的子元素。找到对应的元素

一、基本参数

DEFAULT_INITIAL_CAPACITY:默认容量
DEFAULT_LOAD_FACTOR:默认的负载因子,表示散列链表的使用度,数越大那么使用度越高。
entry:链表对象
table:链表的容器是一个数组
threshold:临界点,当达到这个临界点的时候进行扩容,它等于负载因子*容量大小

二、创建一个HashMap

1.首先会判断初始容量的大小是否符合条件,不能太大也不能太小
2.创建一个Entry的数组
3.根据默认的临界点,计算一个最合适的容量尽量减少碰撞保证capacity(lenght)是n的次方。

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
            initialCapacity = DEFAULT_INITIAL_CAPACITY;
        }

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // Android-Note: We always use the default load factor of 0.75f.

        // This might appear wrong but it's just awkward design. We always call
        // inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
        // to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
        // the load factor).
        threshold = initialCapacity;
        init();
    }
     
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
       //计算一个合理的容量  capacity是n的2次方
        int capacity = roundUpToPowerOf2(toSize);

        // Android-changed: Replace usage of Math.min() here because this method is
        // called from the  of runtime, at which point the native libraries
        // needed by Float.* might not be loaded.
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }

        threshold = (int) thresholdFloat;
        table = new HashMapEntry[capacity];
    }

二、Entry

next:保存当前table位置 下一个entry元素
value:是值


Android HashMap_第1张图片
image.png

二、put方法

1.如果是空健,创建一个空元素entry返回
2.如果不是空,那么根据key的length计算出index---在数组中存放的位置。
3.如果当前位置有元素,看for循环中HashMapEntry e = tab[index]; e != null,那么判断它们的hash值,和健的值是否相等。如果相等新的值会覆盖旧的值,并且返回给客户端之前的值
4.如果table已经满了将当前的table扩大2倍。
5.如果没有覆盖新的元素,那么获取当前table位置链表的头结点,新的元素就放置在头结点的位置,并且它的next指向原来元素,如果原来这个位置上有元素,那么形成链表

  1. int index=hash & (table.length - 1),这里的table.length==capacity==n^2。查看Java7的的资料 当table.length - 1=15和14时,length是16和15。16是4^2而15不是。所以在table.length-1=14时发生的碰撞情况很多。

注意修改了addEntry修改了table[index]的指向。

   @Override public V put(K key, V value) {
        if (key == null) {
    如果是空健,那么创建一个entry对象
            return putValueForNullKey(value);
        }
    计算hash值
        int hash = Collections.secondaryHash(key);
        HashMapEntry[] tab = table;
        int index = hash & (tab.length - 1);
        //遍历数组中的元素
        for (HashMapEntry e = tab[index]; e != null; e = e.next) {
//加入元素的key的hash值和数组中现有元素的key的hash值和内容相同,那么替换它
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

   
        modCount++;

        addNewEntry(key, value, hash, index);
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

三.get方法获取数据

1.首先如果key是空键,判断是否有对应的entry。如果有返回entry存储的值。
2.如果不是空值,根据hash算法以及数组长度计算出index
3.取出数组对应的index位置保存的entry,遍历这个entry(因为它是一个链表),一次循环后,循环值e=e.next(),再进行循环,当e的hash值和key的值相同时取出对应的值

   public V get(Object key) {
        if (key == null) {
            HashMapEntry e = entryForNullKey;
            return e == null ? null : e.value;
        }
        int hash = Collections.secondaryHash(key);
        HashMapEntry[] tab = table;
        for (HashMapEntry e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

四、HashMap的查找

1.遍历数组中所有存储的entry,然后遍历该位置的链表,确认是否有元素

 @Override public boolean containsValue(Object value) {
        HashMapEntry[] tab = table;
        int len = tab.length;
        if (value == null) {
            for (int i = 0; i < len; i++) {
                for (HashMapEntry e = tab[i]; e != null; e = e.next) {
                    if (e.value == null) {
                        return true;
                    }
                }
            }
            return entryForNullKey != null && entryForNullKey.value == null;
        }

        // value is non-null
        for (int i = 0; i < len; i++) {
            for (HashMapEntry e = tab[i]; e != null; e = e.next) {
                if (value.equals(e.value)) {
                    return true;
                }
            }
        }
        return entryForNullKey != null && value.equals(entryForNullKey.value);
    }

HashMap的优缺点

1.它的查找性能很高,根据Hash算法计算出key在整个table数组中的位置,遍历这个数组中的链表找到指定的元素,不需要去一个一个对比。
2.在插入时需要查询该位置是否有相同元素。如果发生hash碰撞会形成链表,所以它的插入效率没有数组高
3.它不是同步的,如果同时操作同一个HashMap会造成数据不一致。

你可能感兴趣的