集合初探--认识Map

taogebx

浏览: 33566 次
性别:
来自: 杭州

最近访客更多访客>>

xiangshouxiyang

omeweb

fogforest

donchiang709

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

java[语言]

数据结构算法 J#设计模式 IBM

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 红黑树算法实现）

·一个关于红黑树系列文章推荐：教你透彻了解红黑树