Java数据结构 — Map_java中有序的map结构有哪些

常用Map：Hashtable、HashMap、LinkedHashMap、TreeMap

类继承关系：

HashMap

1）无序；
2）访问速度快；
3）key不允许重复（只允许存在一个null Key）；

LinkedHashMap

1）有序；
2）HashMap子类；

TreeMap

1）根据key排序（默认为升序）；
2）因为要排序，所以key需要实现 Comparable接口，否则会报ClassCastException 异常；
3）根据key的compareTo 方法判断key是否重复。

HashTable

一个遗留类，类似于HashMap，和HashMap的区别如下：

1）Hashtable对绝大多数方法做了同步，是线程安全的，HashMap则不是；
2） Hashtable不允许key和value为null，HashMap则允许；
3）两者对key的hash算法和hash值到内存索引的映射算法不同。

HashMap

HashMap底层通过数组实现，数组中的元素是一个链表，准确的说HashMap是一个数组与链表的结合体。即使用哈希表进行数据存储，并使用链地址法来解决冲突。

HashMap的几个属性：

initialCapacity：初始容量，即数组的大小。实际采用大于等于initialCapacity且是2^N的最小的整数。
loadFactor：负载因子，元素个数/数组大小。衡量数组的填充度，默认为0.75。
threshold：阈值。值为initialCapacity和loadFactor的乘积。当元素个数大于阈值时，进行扩容。

优化点：

1、频繁扩容会影响性能。设置合理的初始大小和负载因子可有效减少扩容次数。
2、一个好的hashCode算法，可以尽可能较少冲突，从而提高HashMap的访问速度。

添加元素源代码分析：

    public V put(K key, V value) {
   
        if (table == EMPTY_TABLE) {
     //判断是否已经初始化，1.7版本新增的延迟初始化：构造函数初始化后table是空数组，没有真正进行初始化，直到使用时在进行真正的初始化
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);  //计算key的hash值
        int i = indexFor(hash, table.length);  //根据hash值计算数组索引
        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))) {
     //如果key已经存在，新值替换旧值，返回旧值
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    private void inflateTable(int toSize) {
   
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);  //计算不小于toSize且满足2^n的数，算法很巧妙

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//阈值=容量*负载因子，用于判断是否需要扩容，负载因子默认为0.75
        table = new Entry[capacity];  //真正的数组初始化
        initHashSeedAsNeeded(capacity);  //初始化hash种子
    }

    private static int roundUpToPowerOf2(int number) {
   
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    //获取最靠近且大于等于number的2^n:
    //第一种情况number不是2^n，number的二进制的最高位的高一位变为1且其余位变为0，例如14(0000 1110)-->16(0001 0000)。
    //    将number左移1位,相当于最高位的高一位变为1，例如：14(0000 1110)-->28(0001 1100),
    //    计算最靠近且小于等于上一步得到的数的2^n数，相当于其余位变为0，例如：28(0001 1100)-->16(0001 0000)
    //
    //第二种情况number本身就是2^n，按上述步骤计算会得到number*2。例如：16-->32
    //    number - 1的目的是针对number正好是2^n的特殊处理。做减1处理后，number最高位变为0，次高位变为1，再按第一种情况计算得到number本身。
    //由于对本身就是2^n的number的减1处理，当number=1时会出现错误，所以需要对1特殊处理，如果number=1则直接返回1
    //最终得到计算最靠近且大于等于number的2^n的方法：  (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1
    }

    //如果一个数是0, 则返回0；
    //如果是负数, 则返回 -2147483648：
    //如果是正数, 返回的则是跟它最靠近且小于等于它的2的N次方，例如8->8 17->16
    public static int highestOneBit(int i) {
   
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16); //对正数来说,移位完之后为最高位之后都变为1，移5次是因为int为32位，例如：0010010 --->  0011111
        return i - (i >>> 1); //结果为最高位为1，其他位为0，例如0010000，从而得到最靠近且小于等于它的2的N次方。
    }//需要获取资料的朋友请加Q君样：290194256*

    
    //单独处理key为null的情况，放在数组索引位置为0的链表
    private V putForNullKey(V value) {
   
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
   
            if (e.key == null) {
    //如果已经存在key为null的元素，用新值替换调旧值，返回旧值。
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);//如果不存在key为null的元素，在0位置新增key为null的元素，返回null。
        return null;
    }


    //计算key的hash值
    final int hash(Object k) {
   
        int h = hashSeed; //hash种子，1.7版本引入，获取更好的hash值，减少hash冲突；当等于0时禁止调备用hash函数
        if (0 != h && k instanceof String) {
   
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of c
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101