HashMap

发表于 | |
字数统计: 2.5k | 阅读时长 ≈ 10

Map > AbstractMap > HashMap

Map

翻译：

一个键值对的集合。 一个map不能包括重复的key，一个key最多对应一个值。（即通过一个key最多能找到一个值，包括没有值的情况）

这个接口是用来替换的Dictionary类，因为Dictionary是一个抽象类，而不是一个接口。

Map提供了三种观察集合的方式，包括：

  1. a set of keys 键的集合
  2. collection of values 值的集合
  3. set of key-value mappings 键值对的集合

遍历map的顺序，定义为，迭代map并返回集合元素的顺序。每次迭代，得到元素的序列。在具体实现上，每次遍历TreeMap返回的序列顺序是唯一，而HashMap 则不唯一。

在key是可变的变量（即不用final修饰的变量）时，若是该变量的指向对象改变，Map是没有对该行为负责的。（尽量不要使用final的元素作为key）。 Map中是不允许用自身作为它的一个key；若是把自身作为其中一个value，则在比较对象的是否相等的可靠性也不可保证。

通常的Map的实现都提供两个构造方法，一个无参的，一个Map（Map），接受一个map作为参数来作为初始元素。当然这只是个建议，接口没有强制这个建议 手段，但是JDK的中的实现都遵循了这个建议。

有一些方法是没有具体实现的，所以抛出支持该操作的异常。

一个Map的实现，可能会对KEY和Value的类型做限制。比如允许key-value为空的，或对键的类型做限制。不顾这些限制会可能抛出异常。

很多集合框架，都会要求比较的两个对象是非空类型，这里Map不做要求。

一些操作会有’self-referential’的情形，在遍历这个集合时，无论是直接或间接引用自身，有可能要特殊处理。

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
public interface Map<K,V>{
    int size();
    boolean isEmpty();
    boolean containKey(Object key);
    boolean containValue(Object value);
    V get(Object key);
    V put(K key, V value);
    void putAll( Map<? extends K,? extends V> m);
    void clear();
    //下面三个即上面提到的是三种视图。
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K,V>> entrySet();
    
    interface Entry<K,V>{
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equal(Object o);
        int hashCode();
        
            //...一些比较实现，根据Key或Value来排序，或是通过Lamda来暴露比较的算法。
        public static <K extends Comparable<? super K>,V> Comparator<Map.Entry<K,V>> comparingByKey(){}
    }
    
    
    //通过方法，看到Java8提供了default关键字，让接口也能实现方法，（包括声明成员，如下），包括提供了lamda，使得函数也能作为参数。
//    default int value=10;
    default void forEach(BiCosumer<? super Key,? super V> action);
    //... remove(), replace(),merge()操作
    
}

AbstractMap

翻译：

这个类提供了对Map提供了骨架的实现，减轻了子类对Map实现的负担。

要是实现一个不可变的Map，（unmodifiable map），只要继承该类并实现entrySet()方法，也就没有add，remove方法的具体实现，若是调用了直接报异常。 实现一个可变的Map，就要实现add(), remove()方法了，并且在它的迭代器要同时实现添加移除的方法。

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
public abstract class AbstractMap<K,V> implements Map<K,V>{
    //查询操作
    //size(),isEmpty(),containValues(),containKey() get()
    //比如：
    public V get(Object key){
        Iterator<Entry<K,V>> i = entrySet().iterator();
        if(key==null){      //key为null的情况
            while(i.hasNext()){     //先通过hasNext()方法判断在该游标之后是是否仍有元素, 再通过.next()方法获取该元素。
                Entry<K,V> e = i.next();
                if(e.getKey()==null){
                    return e.getValue();
                }
            }
        }else{  //key非空的情况
            while(i.hasNext()){ 
                Entry<K,V> e = i.next();
                if(key.equals(e.getKey())){
                    return e.getValue();
                }
            }
        }
    }
    
    //修改操作
    //put(),remove()
    
    //Bulk Operation批量操作
    //putAll(),  clear()
    
    //Views 查看
    transient Set<K> keySet;
    transient Collection<V> values;
    //keySet(),values(),entrySet()，注意这里的entrySet（）方法是抽象方法。
    
    //Comparing and hashing 一些比较，哈希方法的实现
    
}

HashMap

翻译：

使用了哈希表来实现了Map接口。实现了所有可选的方法，允许key和value为空的情况。 HashMap类似HashTable，不同之处在于HashMap不同步的，且允许null的情况。由于使用Hash表实现的方式，所以遍历是出来的元素顺序不保证相同。

HashMap的在对元素get，put操作时，提供了常量时的性能（时间复杂度为O(1)），前提是哈希函数能够将元素合理地分散在桶子里。（愿译：assuming the has function disperses the elements properly among buckets.） 遍历集合视图（即遍历所有元素）需要时间复杂度n（n=桶子的数量+ 所有链表的元素size之和）。所以在设置初始容量（initial capacity）或是加载因子太低（the load factory）,否则遍历性能会很低。

HashMap有两个参数会决定它的性能，初始容量和加载因子。初始容量就是在在哈希表创建时，桶子的数量，加载因子是表示哈希表多满时 （即装元素的桶子数目/所有桶子数目），容量会自动增加。当前元素数量超出capacity*factor之后，哈希表需要rehashed（内部数据结构重建），表的桶子数量 大约翻倍。

通常说，加载因子默认为0.75，是在时间与空间较合适的选择。加载因子高了，空间利用高，但是在操作上（put，get）花的时间会变高。若是可以提前估计要存放的 的数量，来设置初始容量和加载因子是最好不过的，要是设置初始容量大于实际存放的最大值，过程中就可以避免rehashed。

要是每个entry的hasCode()返回同一值，那么出现一种极端情况，相当于将数据存放在一个链表了，查询速度会很低（O(N)。

HashMap不是线程安全的，若是有多个线程同时访问一个Map，若有一个线程对Map有结构修改，必须在外部保证其线程安全。结构性调整是比如添加，删除，仅是修改 key对应的值是不归于的。具体处理，可以
Map m = Collections.syschronizedMap(new HashMap(…));

在迭代器创建后，有结构性修改发生，除了使用迭代器使用自己的remove方法，会抛出ConcurrentModificationException,即快速失败fail-fast,在 面对不可靠的数据时，尽量快的抛出异常而不是允许数据不可靠。但是，也不可能根据抛异常来判断是否可靠,这个异常仅应该用来检测bug。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Clonable,Seriazable{
    //默认容量16，且容量必须是2的次幂
    static final int DEFAULT_INIT_CAPACITY = 1<<4;
    
    //最大容量
    static final int MAX_CAPACITY = 1<<30;
    
    static class Node<K,V> implements Map.Entry<K,V>{
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
        Node(int hash,K key, V value, Node<K,V> next){
                
        }
    }
    
    transient Node<K,V>[] table;
    
    transient Set<Map.Entry<K,V>> entrySet;
    
    
    int size;
    
    //用来检测fast-failed
    int modCount;
    
    
    //get方法
    public V get(Object key){
        Node<K,V>e;
        //试图获取entry，若不为空，则返回其值
        //问题归于找到entry, 如何找到hash值
        
        return (e = getNode(hash(key), key)) == null ? null :e.value;
    }
     static final int hash(Object key) {
            int h;
            //这里为了让hash值分布更加均匀
            //若是一部分的数，生成的都小于2^16，则会使得元素都放在table前面，下面这个操作
            //原本 h=0000 1011    //假设只有8位，32位同理
            //经过这个操作后：0100 1101 
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //这里使用无符号右移，
            //有符号右移需要区分数字的正负，正数右移高位补0，负数右移高位补1
    }
    
    public Node<K,V> getNode(int hash, Object key){
        Node<K,V>[] tab; Node<K,V> first, e ; int n; K k;
        if((tab=table)!=null && (n = tab.length)>0 
        && (first=tab[(n-1)& hash]) !=null){    //找到的第一个元素是
        //这里n-1 转为二进制 0111 1111 
        //index = 0111 1111 & 0100 1101 = 1100 1101   
        //这里为什么要用n-1再与操作，是因为，Int类型中最高位仅是用来存放符号
           if((first.hash==hash && 
           ((k=first.key)==key) || (key!=null && key.equals(k))))
               return first;
           
           if((e=first.next) != null){    //first仅仅是作为一个头部，不存放数据
               if(first instanceof TreeNode){       //要是表头，即使红黑树，使用红黑树搜索
                   return ((TreeNode<K,V>)first).getTreeNode(hash, key);    //从当前链表（红黑树了）获取合适的节点
               }
               //否则，是一个常规的链表，一个个比对搜搜 
               do {
                   if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                       return e;
               } while ((e = e.next) != null);
               
           }
        }  
         
    }
}

关于普通对象重写的hashcode(), equals()方法的常见问题

重写一个bean类时，使用idea右键generate重写两个方法

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
public class A {
    int a, b;
  
    @Override
    public boolean equals(Object o) {
      	// 判断两个不同对象是否相同，先判断对象的class是否相同，再判断关键的属性的是否相同
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        A a1 = (A) o;
        return a == a1.a && b == a1.b;
    }

    @Override
    public int hashCode() {
      	// 使用工具类算出相应的 hashcode
        return Objects.hash(a, b);
    }
}

// Objects.java

    public static int hashCode(Object a[]) {
        if (a == null)
            return 0;

        int result = 1;
				// 对于关注的几个属性，如何生成一个hash的算法
      	// 使用质数31乘以当前值，
        for (Object element : a)
            result = 31 * result + (element == null ? 0 : element.hashCode());

        return result;
    }