Map接口与学习系列(二)---LinkedHashMap

原创
2016/09/10 10:47
阅读数 22
  • HashMap的实现是Hash表,健值对都是无序的。
  • TreeMap 的实现是红黑树结构,根据key排序,默认是升序,也可以自定义排序器的顺序
  • LinkedHashMap 保存了插入的顺序,保证输出的值与输入的顺序相同。
  • Hashtable 是同步的,有同步的开销。

HashMap是一个比较基础的Map的实现,HashMap的读取是无序和随机的。LinkedHashMap是继承自HashMap,并提供了HashMap没有的特性:保持数据的顺序读写,即可以根据输入的顺序输出。

TreeMap也可以保证顺序读写,TreeMap的底层数据结构是红黑树,读写的算法复杂度为O(logn),而LinkedHashMap的读可以达到O(1),在性能上面比TreeMap更好一些。

LinkedHashMap保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.在遍历的时候会比HashMap慢。

private transient Entry<K,V> header;
//accessOrder 标记是否为访问顺序,true是访问顺序,false为插入顺序,在初始化map的时候,默认为false
private final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}

在HashMap父类中定义了init方法,但实现是空的,在LinkedHashMap中实现如下:header链表初始化。

void init() {
    this.header = new LinkedHashMap.Entry(-1, (Object)null, (Object)null, (java.util.HashMap.Entry)null);
    this.header.before = this.header.after = this.header;
}

LinkedHashMap的put方法没有重写,采用的是父类的put方法,先看下HashMap.put()的源码:

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    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;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}
/**
 * Inserts this entry before the specified existing entry in the list.
 */
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

 

再次看下get方法的源码:

public V get(Object var1) {
    LinkedHashMap.Entry var2 = (LinkedHashMap.Entry)this.getEntry(var1);
//getEntry方法是使用父类HashMap的方法。
    if(var2 == null) {
        return null;
    } else {
var2不为空的时候,记录下写入顺序。
        var2.recordAccess(this);
        return var2.value;
    }
}
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    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 != null && key.equals(k))))
            return e;
    }
    return null;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部