18°

HashMap

常用的顺序表有ArrayList, 链表有LinkList,而顺序表在查询数据的时候很快,但是增加和删除数据的时候相对较慢,因为每次增加或者删除的时候都需要将后续的数据向前或向后位移,所以在顺序表进行删除的时候要从尾部向前进行for循环进行删除,否则会报角标越界,也可以使用迭代器进行删除

而链表在增加和删除方面很快,因为链表本身包括两部分,一块是数据,另一块是指针(当然循环链表有两个指针.这里只说单链表的),删除或者增加数据的时候, 只是把指针的指向改一下,数据不需要移动,所以很快,例如在A和B之间插入数据C,只需要把A的指针指向C,把C的指针指向B就可以了

而HashMap是结合了顺序表和链表的优点,并采用hash算法进行排序,其中最主要的两个方法就是put 和get的方法

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
    modCount++;
    addEntry(hash, key, value, i);
    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);
    }
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);
    }

原理就是: 在put的时候,先对key进行hashCode计算,然后通过对hashCode和数组的长度进行求莫,这两步其实就是所谓的hash算法,求莫得出的值就是在数组table中所在位置的下标,而put函数中的for循环,是为了遍历在节点上的Entry,先判断通过key得到的hashcode和key是否一样,一样的话就将新的取代旧的,而addEntry就是将key-value添加到链表中,hashmap默认加载容量是16,加载因子是0.75,,这里的threshold就是16*0.75,如果链表中加载的下一个key-value的所在位置大于最大容量了rhredhold,就进行扩容,并且扩容后重新计算链表的长度,每次直接扩大原来的两倍,例如16,直接扩成32, 所以容易造成内存浪费,所以new hanshmap的时候最好指定一个大小,而这大小最好略大于存储的容量.如果不大于最大容量就直接创建Entry,new 一个hanshMapEntry,并将key-value,hashcode都存进去

而get方法其实差不多,也先计算key的hashcode,求出在table中的下标,再遍历这个下标上所有的entry,key和hashcode都相等,就取出来返回

hash冲突

    指不同对象的hashcode莫以长度出来的角标相同

本文由【Magic_锋】发布于开源中国,原文链接:https://my.oschina.net/fbf8866/blog/3159070

全部评论: 0

    我有话说: