Java常用类库之Map集合_map是一个键值对的集合,存储的键与值相互映射,键值是不可重复的,其结构为hashset

Map集合

• 单值存储取1个值Collection
  • 不允许重复的Set
  • 允许重复的List
• 双值存储Map:每次存储的是一个键值对数据

Map集合存储的是一个个的键值对数据，Map集合的键(key)不可重复,将键映射到值的对象。Map不能包含重复的键; 每个键最多可以映射一个值。

在Set集合中有HashSet和TreeSet，但他们分别使用了HashMap和TreeMap，实际上是使用了双值存储的Map来存储单值。Set集合(HashSet, TreeSet, LinkedHashSet)的内部使用了Map集合并且只使用了key的位置来存储数据，从而实现了本身的内容不可重复。

用完要删掉集合中的数据，否则会占用内存，所以有时候用remove取出并删除数据

HashMap

对哈希表实现采用对象数组+链表，链表长度达到一定值会转换成二叉树

哈希码(hasgCode)，int，对散列表（哈希表）的性能进行了优化，同一类相同属性的哈希值最好不同

哈希表生成

1. 万物皆对象，根据对象生成对应的哈希值 (hashCode = 12313)
2. 哈希值根据数组的长度取模 (hashCode%length = 12313%16)
3. 将该对象存在索引对应的位置

因此在查询该对象时就可以通过对哈希值取余找到他在哈希表中的位置，而不需要遍历。

对于同一个哈希表，由于多个哈希值取模的结果可能相同，会在其取模结果所对应的位置加入链表（哈希桶），当哈希桶中的数据量大于8时，链表会转换成红黑二叉树，更利于查找；但是当哈希桶中的数据量减小到6时，又会从红黑树转换为链表。

• 初始桶的数量：16
• 散列因子： 0.75
• 当所有的哈希桶中有75%已经存入数据，就会对桶扩容到原长度的两倍。
• 要合理设置初始容量，避免重复存储（不断重建数据结构）
• 散列因子越大，越节省空间，查询效率低；散列因子越小，越浪费空间。查询效率越高。

HashMap/Hashtable/ConcurrentHashMap
TreeMap
LinkedHashMap
的使用与HashMap操作是一样的，指示由于数据结构的差别，存储顺序不同

HashMap部分源码分析

public V put(K key, V value) {
    //通过 键 得出哈希值
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    //如果为空数组，执行扩容算法resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    //位运算 与 相当于哈希值对length取余，算出下标，如果无数据，插入新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //判断 键 是否存在，比较哈希值相同且键完全一样
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //插入链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        //键已经存在
        if (e != null) { // existing mapping for key
            //先取出旧的值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            //赋值
                e.value = value;
            afterNodeAccess(e);
            //返回旧值
            return oldValue;
        }
    }
    ++modCount;
    //如果超过阈值，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

HashMap的遍历

使用keySet()返回全部的键，通过get()获取其对应的值

HashMap<String, String> data = new HashMap<>();

//将键值对放入表中
data.put("key1", "锄禾日当午");
data.put("key2", "汗滴禾下土");

//取得key的value值
String value1 = data.get("key1");
String value2 = data.get("key2");

//取得所有的key值，放在一个集合中.通过forEach迭代读取key值并返回value值
Set<String> set = data.keySet();
for (String s:set) {
    System.out.println(s);
    System.out.println(data.get(key));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

map集合各子类区别分析

• HashMap 线程不安全，效率高
• Hashtable 线程安全，效率低
• ConcurrentHashMap 采取分段锁机制，保证线程安全，效率比较高
• TreeMap 使用二叉树自动排序存储，HashMap不保证存储顺序
• LinkedHashMap 既在哈希表中，又在双向链表中

存储自定义对象时需要注意的问题

这里使用book类作为键。系统通过计算出book1的哈希值将他和对应的值存放在某个桶中。此时如果改变book1的内容，则存在表中的键的内容也发生了改变，但是由原键计算出的位置没有变。

此时用book1搜索时，会先根据新的内容返回哈希值，结果就是get()方法无法找到它原哈希值所在的位置，也就不能通过这个键找到原来的值。

此时如果新建一个与原来相同的键book3，虽然可以定位到原来的book1哈希值所对应的位置，但是在进行equals验证内容时，无法匹配，同样返回不了原值

所以当一个对象作为计算哈希值（键）的对象存储时，不要改变它，否则会出现哈希值错乱

HashMap<Book, String> data = new HashMap<>();
Book book1 = new Book("金苹果","xxxxxx");
data.put(book1,"第一本书");
Book book2 = new Book("小王子","xxxxxx");
data.put(book2,"第二本书");
book1.setName("银苹果");
//当一个对象作为计算哈希值（键）的对象存储时，不要改变它，否则会出现哈希值错乱
System.out.println(data.get(book1));
//null

Book book3 = new Book("金苹果","xxxxxx");
//null
//哈希值虽然可以找到该对象，但是equals不能满足，仍然找不到该对象
1
2
3
4
5
6
7
8
9
10
11
12
13