`
taogebx
  • 浏览: 33675 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

集合初探--认识Map

阅读更多
1. HashMap

A)底层数据结构


·HashMap存储结构是由数组与单向链表构成(Hash表),如上图:水平方向是一个Entry数组,垂直方向是一个单向链表,每个数组元素都是单向链表的头,每个单向链表元素都具有相同index值(散列值)。
·这种结构决定了HashMap存取很快:由元素hash值确定操作哪个单向链表,影响的元素只涉及到某个链表,这就是所谓的“桶”机制(简单说不同的东西放在不同的位置,需要时才能快速找到)。
·HashMap每一个元素(数组或链表中的元素)都是一个包含四个属性:key,value,hash,next的一种数据结构,其中next指向链表中下一个元素;hash存储的是每个元素key的hash值。
·如果存在key=null的元素,则一定存在table[0]位置。上图table[0]链表后还有元素,这种情况若要发生,只有当元素的hash值为0的情况,index才为0。



·loadFactor--负载(装载)因子,定义为:散列表的实际元素数目(n)/散列表的容量(m)。负载因子与HashMap resize有关。默认值为DEFAULT_LOAD_FACTOR=0.75。
    ·负载因子衡量的是一个散列表的空间的使用程度,越大表示散列表的装填程度越高,反之愈小。
    ·对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),如果负载因子越大,空间利用更充分,但查找效率会降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。
·capacity:HashMap容器大小,也就是数组table[]长度。默认值为DEFAULT_INITIAL_CAPACITY=16。最大值是MAXIMUM_CAPACITY=1 << 30。
·table(Entry[] table):即为上面数据结构图中X方向的数组。
·threshold :HashMap resize的临界值,即当HashMap中元素个数达到该值时,HashMap就会调用其resize方法,重新扩充大小。
·Entry:HashMap中的静态内部类。HashMap每个元素的实际存储结构。

B)构造方法

//默认构造方法
public HashMap(){
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
} 
// 以指定初始化容量、负载因子创建 HashMap 
public HashMap(int initialCapacity, float loadFactor) { 
    if (initialCapacity < 0) 
        throw new IllegalArgumentException( "Illegal initial capacity: " + initialCapacity); 
    if (initialCapacity > MAXIMUM_CAPACITY) 
		initialCapacity = MAXIMUM_CAPACITY; 
	if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
		throw new IllegalArgumentException(loadFactor); 
		
	// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
	int capacity = 1; 
	while (capacity < initialCapacity) 
		capacity <<= 1; 

	this.loadFactor = loadFactor; 
	// 设置容量极限等于容量 * 负载因子
	threshold = (int)(capacity * loadFactor); 
	// 初始化 table 数组
	table = new Entry[capacity]; 		
	init(); 
} 

·构造HashMap:重点在于Entry对象数组的构造。
·可以看出,Entry数组大小capacity一定是2的倍数:即默认大小为16,或可以由传入参数initialCapacity控制,最终capacity也是>= initialCapacity的2的倍数。
·threshold的计算:capacity * loadFactor;loadFactor默认0.75,可以参数传入。

B)插入对象

public V put(K key, V value) {
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
    if (key == null)
        return putForNullKey(value);
    // 根据key的keyCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
    for (Entry<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;
        }
    }
    // 如果i索引处的Entry为null,表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的Entry放入bucketIndex索引处,并让新的Entry指向原来的Entry
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    // 如果Map中的key-value对的数量超过了极限
    if (size++ >= threshold)
        resize(2 * table.length); // 把 table对象的长度扩充到原来的2倍。
}

·设计思路:先计算hash值,根据hash值得到数组的位置index,然后遍历单向链表,找到插入位置。
·key为null时,会调用putForNullKey,通过代码,会发现一定会存放在table[0]中。
·key不为null:检查hash值,key是否相等。全相等则替换value。不全相等,则添加Entry,位置为table[index]链表头。
·key的hash值决定Entry对象的存储位置。当两个Entry对象的key的hashCode()返回值相同时,将由key通过eqauls()比较决定是否覆盖Entry对象的value,还是新增一个Entry对象。这就是为啥基于hash散列的集合在覆盖eqauls()的同时要覆盖hashCode()。
·Entry数组扩容:数组元素达到threshold时扩容为原数组2倍大小,if (size++ >= threshold) resize(2 * table.length)。
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int) (newCapacity * loadFactor);
} 

    ·当HashMap中元素不断增加的时候,hash冲突的概率也越来越高,因为数组长度是固定的。为减少冲突,提高查询的效率,就要对HashMap的数组进行扩容。
    ·扩容数组,不会重新计算hash值,但会重新计算每个元素的index值,这是比较消耗性能的。
    ·已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。(除非确认个数不会变化,才有意义)。
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K, V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K, V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}


·hash值的计算
int hash = hash(key.hashCode());
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

    ·先调用Object的hashCode(),这是个native方法。
     ·然后会重新进行hash:目的在于二进位分布均匀,最后计算出的数组位置相对分布均匀,冲突的概率降低。(均匀散列)
很明显了,它的目的是让“1”变的均匀一点。

·Entry数组index的计算
int i = indexFor(hash, table.length);
static int indexFor(int h, int length) {
    return h & (length-1);
}

    ·要保证所有hash值对应的散列值落在table 数组索引0到table.length-1位置:采用取模运算hash % table.length,元素的分布相对来说是比较均匀。
    ·取模运算效率比较低,实现的时候采用与运算替代方案,这是基于:
         ·hash % table.length = hash & (2^P -1) = hash & (table.length - 1)
         ·2^P -1,二进制数据从低到高(右到左)P-1位是全1,其余全0,hash & (2^P -1)一定小于table.length ,保证散列值全落在0到table.length-1位置上。
         ·散列值分布相对均匀,先看个例子:假设数组长度分别为15和16,优化后的hash码分别为8和9,那么&运算后的结果如下:

            很明显table.length是偶数时,冲突的可能性更小。这就是为什么capacity的值一定是2的倍数。

C)get对象,remove对象

·跟插入对象思路一样:先计算hash值,根据hash值得到数组的位置index,然后遍历单向链表,找到相应位置。

D)遍历对象

·KeySet遍历HashMap
    for(Iterator ite = map.keySet().iterator(); ite.hasNext();){
        Object key = ite.next();
        Object value = map.get(key);
    }
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }
   
    ·使用KeySet遍历,会进行两次循环,并且进行两次hash值计算,性能低下。

·EntrySet遍历HashMap(推荐的方式)
    for(Iterator ite = map.entrySet().iterator(); ite.hasNext();){
        Map.Entry entry = (Map.Entry) ite.next();
        entry.getKey();
        entry.getValue();
    }
   
    ·直接返回其保存key-value的原始数据结构Entry对象,遍历一次,并且无需进行耗费时间的hashCode计算。

E)其他

·HashMap是线程不安全的,如果被多个线程共享的操作有可能导致cpu 100%。
    ·原因在于: 数据扩容时,将数据从旧容器转移到新容器(transfer方法),并发情况下会导致“e.next()永远都不会为null”,进入死循环。参考HashMap死循环的探究

2.LinkedHashMap

A)底层数据结构


·LinkedHashMap继承于HashMap,其基本操作与父类HashMap相似,通过重写父类相关方法,实现其特性。
·Entry也继承于HashMap中的Entry,但增加了两个属性:before--指向上一个Entry;after--指向下一个Entry,从而在哈希表的基础上又构成了双向链接列表。

·可以看出底层使用哈希表与双向链表来保存所有元素。除了通过增加header来作为双向链表的头元素,其哈希表存储方式跟HashMap完全一样。即有HashMap快速随机存取的特点,又能支持顺序遍历所有元素。
·按照何种顺序遍历是由accessOrder决定,accessOrder为false--插入顺序(上图即为插入三个元素后的结构,遍历顺序为header->1->2->3),为true--访问顺序。默认为插入顺序。

B)构造方法

public LinkedHashMap() {
    super();
    accessOrder = false;
} 

void init() {
    header = new Entry<K,V>(-1, null, null, null);
    header.before = header.after = header;
}

·LinkedHashMap重写了init()方法,在调用父类的构造方法完成构造后,进一步实现了对其元素Entry的初始化操作。从而实现双向链表的功能。

C) 插入对象
  
·LinkedHashMap只重写了父类HashMap的put方法调用的子方法addEntry(...) 和createEntry(...),从而实现双向链接的特性。

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 调用create方法,将新元素以哈希表与双向链表的的形式加入到映射中。
    createEntry(hash, key, value, bucketIndex);

    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) { // 检查是否需要删除最近最少使用元素
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);// 将元素加入到哈希表。
    table[bucketIndex] = e;
    // 调用元素的addBrefore方法,将元素加入到双向链接列表。
    e.addBefore(header);
    size++;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

    ·每次元素都是插入到table[index](hash表单链表表头),双链表header之前。  
     ·元素插入后会检查是否需要删除最近最少使用元素。若果需要,则删除header.after指向的元素。默认返回false,不移除最旧元素。
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

        ·可以覆盖此方法:元素达到100个删除最旧的条目。配合accessOrder=true使用,就可以实现一个LRU的策略。
        private static final int MAX_ENTRIES = 100;
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > MAX_ENTRIES;
        }

    ·扩容策略跟HashMap一样,2倍大小。

D) get对象

   ·LinkedHashMap重写了父类HashMap的get方法,但实际先调用父类HashMap的getEntry()方法(HashMap的get()方法功能一样)取得元素。
   ·取得查找的元素后,再判断当前排序模式accessOrder为true时--记录访问顺序,将最新访问的元素添加到双向链表header之前,并从原来的位置删除。
   ·由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。
public V get(Object key) {
    // 调用父类HashMap的getEntry()方法,取得要查找的元素。
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    // 记录访问顺序。
    e.recordAccess(this);
    return e.value;
}

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    // 如果定义了LinkedHashMap的迭代顺序为访问顺序,
    // 则删除以前位置上的元素,并将最新访问的元素添加到链表header之前。
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}


3.TreeMap

·TreeMap底层采用一棵“红黑树”来保存集合中的 Entry(详细代码分析,学习红黑树算法后再来看,感兴趣的可以先参考:通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

·一个关于红黑树系列文章推荐:教你透彻了解红黑树
  • 大小: 22.5 KB
  • 大小: 34.4 KB
  • 大小: 20.6 KB
  • 大小: 21.4 KB
  • 大小: 47.7 KB
  • 大小: 38.8 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics