Java数据结构之——Map - 高飞网
398 人阅读

Java数据结构之——Map

2017-07-28 02:09:46

java.util.Map<K, V>

    Map是一个将key映射到value的对象。一个map不能包含相同的key;每个key最多只能映射到一个value。

    Map接口代替了Directory抽象类。Map提供了三种不同的集合视图,这允许一将一个map中的内容作为一个包含key的set或者value的set,或者k-v的set。Map的顺序定义为Map集合视图的迭代器返回的元素顺序。有些Map实现了,比如TreeMap,有些有没,如HashMap。

    注意:如果使用了可变对象的key一定要小心。在Map中的一个key,如果它的对象的变化引起了equals结果的化,则它的行为不确定的。一个特殊的例子是,将map本身做为一个key,如果这发生了,建议是:在这个map上不要定义equals和hashCode方法了。

    所有的多用途Map实现类都应提供两个“标准的”构造器,一个是无参构造,用以创建空Map;另一个是只接收一个Map类型的参数,用以创建一个新的Map,与给定的Map有相同的key-value。实际上,后面的构造器允许用户去copy一个任何一个map,生成一个相同的Map。没有办法强制这么做(只为接口中不能包含构造器),但JDK的实现类者遵循了这个原则。

    该接口包含了“破坏性”的方法,即:正在操作的Map的方法,如果Map不支持这种操作,就会抛出指定的UnsupportedOperationException 异常。如果是这样,这些方法将会抛出UnsupportedOperationException异常,但如果这些调用不影响map,就不必要这么做。例如。在一个不可修改的map上(unmodifiable )调用putAll方法,如果其中没有重叠的key的话,就不必抛出异常了。

     有些map实现类对它们包含的key-value有一定的限制。比如有些不允许null的key,有些限制类型。如果尝试插入一些非法的key或value,将会抛出未检查异常,NullPointerException或ClassCastException。尝试查询这种非法的key是否存在,也将抛出异常,或者直接简单的返回false。 

    该接口是Java集合框架(Collections Framework)。

    在集合框架中的很多方法定义都依据equals方法。例如containsKey(Object key),方法描述为:如果map包含一个指定的key,则返回true。通常情况下,当且仅当map映射一个Key k,如key==null?k==null:key.equals(k)。map中最多包含一个这样的映射。





 

HashMap

HashTable

描述

基于哈希表的Map接口的非同步实现

public class HashMap<K,V>

    extends AbstractMap<K,V>

    implements Map<K,V>, Cloneable, Serializable

哈希表
public class Hashtable<K,V>

    extends Dictionary<K,V>

    implements Map<K,V>, Cloneable, java.io.Serializable

底层结构

数组+链表:
transient Entry[] table;  //
数组

static class Entry<K,V> implements Map.Entry<K,V> { 

    final K key; 

    V value; 

    Entry<K,V> next;//链表 

    final int hash; 

}

数组+链表

 

特性

线程安全性

非线程安全

线程安全,几乎全部使用了synchronized关键字,是对全表的锁同步(包括读和写),效率低下,建议使用ConcurrentHashMap

Null

Nullkeyvalue,不hash,直接放到table[0]

不允许(key & value),会抛出NullPointerException

空间

默认大小

16

11

最大

1 << 30

 

增长因子

0.75f

0.75f

增长动因

size大小大于容量的0.75时,增长为原来的2

size大小大于容量的0.75时,增长为原来的2

增长方式

重新计算hash,重新放值
hash
算法:
int hash = hash(key.hashCode());
static int hash(int h) { 

    h ^= (h >>> 20) ^ (h >>> 12); 

    return h ^ (h >>> 7) ^ (h >>> 4); 

}
static int indexFor(int h, int length) { 

    return h & (length-1); 

}
等同于取模,但性能更好。

重新计算hash,重新放值

hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;

获取索引位置时直接取模

性能优化点

同,ArrayList,事先知道总数的情况下初始化空间大小,避免扩容时的重新hash

 



 

LinkedHashMap

ConcurrentHashMap

描述

基于哈希表的Map接口的非同步实现,具有可预知的迭代顺序(默认为插入顺序)

public class LinkedHashMap<K,V>

    extends HashMap<K,V>

    implements Map<K,V>

哈希表
public class Hashtable<K,V>

    extends Dictionary<K,V>

    implements Map<K,V>, Cloneable, java.io.Serializable

底层结构

双向链表+哈希表:
class Entry<K,V> extends HashMap.Entry<K,V> {

        // These fields comprise the doubly linked list used for iteration.

        Entry<K,V> before, after;

}

其中accessOrder默认为false即插入顺序,如果设置为true,则会将访问的元素放在最后面,是典型的LRU算法

如:

public static void main(String[] args) {

        Map<String, String> map = new LinkedHashMap<String, String>(16, 0.75f, true);

        map.put("a", "a");

        map.put("b", "b");

        map.put("c", "c");

        map.get("b");

        map.get("c");

        map.get("b");

        map.get("a");

        map.get("a");

        map.get("b");

        System.out.println(map);//{c=c, a=a, b=b}

}

/(segment)+数组+链表

class Segment<K,V> {

         transient volatile HashEntry<K,V>[] table;

        transient int count;

        transient int modCount;

        transient int threshold;

        final float loadFactor;

}

class HashEntry<K,V> {

        final int hash;

        final K key;

        volatile V value;

        volatile HashEntry<K,V> next;

}

特性

线程安全性

非线程安全

线程安全。ConcurrentHashMap默认情况下有16个桶,最大有32个,由于是桶锁,写操作最大可支持32个线程并发,读操作全并发。

Null

允许Nullkeyvalue,不hash,直接放到table[0]

不允许(key & value),会抛出NullPointerException

空间

默认大小

16

11

最大

1 << 30

 

增长因子

0.75f

0.75f

增长动因

size大小大于容量的0.75时,增长为原来的2

size大小大于容量的0.75时,增长为原来的2

增长方式

重新计算hash,重新放值
hash
算法:
int hash = hash(key.hashCode());
static int hash(int h) { 

    h ^= (h >>> 20) ^ (h >>> 12); 

    return h ^ (h >>> 7) ^ (h >>> 4); 

}
static int indexFor(int h, int length) { 

    return h & (length-1); 

}
等同于取模,但性能更好。

重新计算hash,重新放值

hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;

获取索引位置时直接取模

性能优化点

 

 




还没有评论!
54.82.57.154