Ø map中的每个成员方法由一个关键字（key）和一个值（value）构成。map接口不直接继承于collection接口，因为它包装的是一组成对的“键-值”对象的集合，而且在map接口的集合中也不能有重复的key出现，因为每个键只能与一个成员元素相对应。
Ø map接口的子接口以及主要实现类有：
子接口：bindings、concurrentmap、concurrentnavigablemap、messagecontext、logicmessagecontext、navigablemap、soapmessagemap、sortedmap
实现类：abstractmap, attributes,authprovider, concurrenthashmap, enummap,concurrentskiplistmap,hashmap, hashtable, identityhashmap, linkedhashmap, printerstatereasons,properties,provider, renderinghints,
simplebindings, tabulardatasupport,treemap,uidefaults,weakhashmap
map接口中定义的方法清单：
Ø map中定义的方法说明：
在map接口中定义的通用方法并不是很多。
a) 添加和删除map中的某个元素
• put(k, v) ： 将给定的“键-值”对放入到给定的map当中
• putall(map<? extends k, ? extends v) : 将指定的map中的“键-值”对放入到给定的map当中
• remove(object key) : 从该集合中移除指定的对象，并返回对应的value
• clear() : 清空map中的所有对象
b) 查询与map有关的数据
• int size() : 返回此map中“键-值”对的个数
• boolean isempty() : 判断此map中“键-值”对的个数是否为0
• boolean containskey(object key) : 测试此map中是否有该key
• boolean containsvalue(object value) : 测试此map中是否包含该value
• v get(object key) : 通过指定的key查询map中对应的value
• collection<object value> values() : 取得map中所有的value
• set<object key> keyset() : 取得当前map中key的集合
• set<entry<k, v>> entryset() : 取得当前map中entry的集合
hashmap实现了map、clonemap、serializable三个接口，并且继承自abstractmap类。
hashmap基于hash数组实现，若key的hash值相同则使用链表方式进行保存，详见hashset中的说明。我引用网上一个名词叫“链表散列”来形容这样的数据结构。
新建一个hashmap时会初始化一个大小为16，负载因子为0.75的空的hashmap。
<span style="font-size:10px;">1. /**
2. * the table, resized as necessary. length must always be a power of two.
3. */
4. transient entry[] table; </span>
那么entry到底是怎么实现的呢？
1. static class entry<k,v> implements map.entry<k,v> {
2. final k key;
3. v value;
4. entry<k,v> next;
5. final int hash;
6. ......
上面代码其实告诉我们entry是一个结点，它持有下一个元素的引用，这样就构成了一个链表。
那么，整体上来说hashmap底层就是使用这样一个数据结构来实现的。
我们提到使用hash，但是hash值如何与元素的存储建立关系呢？（hash算法）
在数据结构课中我们学习过hash的简单算法，就是给你一个hash因子，通过对该元素的hashcode简单的求余，来实现对其快速的定位和索引。
在hashmap中有这样的代码：
1. /**
2. * returns index for hash code h.
3. */
4. static int indexfor(int h, int length) {
5. return h & (length-1);
6. }
这个方法在hashmap中非常重要，凡是与查询、添加、删除有关的方法中都有调用该方法，为什么这么短的一个代码使用率这么高？根据代码注释我们知道，这个方法是根据hashcode及当前table的长度（数组的长度，不是map的size）得到该元素应该存放的位置，或者在table中的索引。
现在我们需要看一下当数据量已经超过初始定义的负载因子时，hashmap如何处理？
在hashmap中当数据量很多时，并且已经达到了负载限度时，会重新做一次哈希，也就是说会再散列。调用的方法为resize()，并且java默认传入的参数为2*table.length。先看一下jdk源码：
1. /**
2. * rehashes the contents of this map into a new array with a
3. * larger capacity. this method is called automatically when the
4. * number of keys in this map reaches its threshold.
5. *
6. * if current capacity is maximum_capacity, this method does not
7. * resize the map, but sets threshold to integer.max_value.
8. * this has the effect of preventing future calls.
9. *
10. * @param newcapacity the new capacity, must be a power of two;
11. * must be greater than current capacity unless current
12. * capacity is maximum_capacity (in which case value
13. * is irrelevant).
14. */
15. void resize(int newcapacity) {
16. entry[] oldtable = table;
17. int oldcapacity = oldtable.length;
18. if (oldcapacity == maximum_capacity) {
19. threshold = integer.max_value;
20. return;
21. }
22.
23. entry[] newtable = new entry[newcapacity];
24. transfer(newtable);
25. table = newtable;
26. threshold = (int)(newcapacity * loadfactor);
27. }
28.
29. /**
30. * transfers all entries from current table to newtable.
31. */
32. void transfer(entry[] newtable) {
33. entry[] src = table;
34. int newcapacity = newtable.length;
35. for (int j = 0; j < src.length; j++) {
36. entry<k,v> e = src[j];
37. if (e != null) {
38. src[j] = null;
39. do {
40. entry<k,v> next = e.next;
41. int i = indexfor(e.hash, newcapacity);
42. e.next = newtable[i];
43. newtable[i] = e;
44. e = next;
45. } while (e != null);
46. }
47. }
48. }
看到这里我们会发现resize（再哈希）的工作量是不是很大啊。再哈希是重新建一个指定容量的数组，然后将每个元素重新计算它要放的位置，这个工作量确实是很大的。
这里就产生了一个很重要的问题，那就是怎么让哈希表的分布比较均匀，也就是说怎么让它即不会成为一个单链表（极限情况，每个key的hash值都集中到了一起），又不会使hash空间过大（导致内存浪费）？
上面两个问题一个是解决了怎么计算hash值快速存取，一个是怎么实现再哈希，何时需要再哈希。快速存取的前提是元素分布均匀，不至于集中到一点，再哈希是元素过于零散，导致不断的重新构建表。
那么在第一个问题中我们看到了这样一个代码return h & (length-1);在第二个问题中我们说过内部调用传入的值为2*table.length;并且默认情况下hashmap的大小为一个16的数字，除了默认构造提供大小为16的空间外，如果我们使用
public hashmap(int initialcapacity,float loadfactor)
上面的构造方法，我们会发现这样的代码：
1. // find a power of 2 >= initialcapacity
2. int capacity = 1;
3. while (capacity < initialcapacity)
4. capacity <<= 1;
5. ……
6. table = new entry[capacity];
也就是说当我们传入1000时，它并没有给我们构造一个容量为1000的哈希表，而是构建了一个容量为1024大小的哈希表。
从整体上我们发现一个问题，那就是无论什么情况hashmap中哈希表的容量总是2的n次方的一个数。并且有这样一个公式：
当length=2^n时，hashcode& (length-1) == hashcode % length
也就是这一点验证了第一个问题，hash索引值的计算方法其实就是对哈希因子求余。只有大小为2的n次方时，那样的计算才成立，所以hashmap为我们维护了一个这样大小的一个哈希表。（位运算速度比取模运算快的多）
c) hashmap的使用方法：
我在很多代码中都用到了hashmap，原因是首先它符合存储关联数据的要求，其次它的存取速度快，这是一个选择的问题。
比较重要的是hashmap的遍历方法,keyset,entryset。
1. hashmap采用数组方式存储key，value构成的entry对象，无容量限制。
2. hashmap基于key hash寻找entry对象存放到数组的位置，对于hash冲突采用链表的方式来解决。
3. hashmap在插入元素时可能要扩大数组的容量，扩大容量时对所有的数据要重新计算哈希和存放到新数组中。当元素个数size大于threshold扩容threshold = (int)(newcapacity* loadfactor);
4. hashmap保证数组的大小为2的指数大小。
5. hashmap非线程安全。
1. hashmap从java1.2后开始引进。hashtable从java1.0开始引入。hashtable一开始基于继承陈旧的抽象类dictionary实现,后面也实现了map接口。hashmap基于map接口实现。
2. hashmap允许存放key为null，value为null。对于key为null时，hashmap首先获取entry数组中的第一个entry对象，并基于entry对象的next遍历链表，当找到其中entry对象的key属性为null时，更新其value值。如果没有key属性为null的entry，则调用addentry(int hash, k key, v value,
int bucketindex)，参数为0,null,value,0，增加一个entry对象，增加时先获取当前数组的第一个entry对象，记为e，然后创建一个key为null，value为传入值得得entry对象，next为之前获取的e。数组的第一个entry对象链表，赋为新创建的entry对象。由此，addentry链表倒序插入元素的。hashtable不允许key为null或value为null，否则会抛出nullpointerexception。这从put方法的源码中很容易看出来，置于为什么真么限制，不明白？
3. hashmap是非线程安全；hashtable是线程安全的，其方法包含synchronized关键字实现线程安全。
4. hashmap的计算hash值方法如下：首先对key取其hashcode,然后通过如下计算：
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h>>> 4);
最后取index时：return h &(length-1);
hashtable计算hash值，直接去key的hashcode值，如下：
int hash =key.hashcode();
取index时：int index = (hash& 0x7fffffff) % tab.length;
5. hashmap和hashtable默认构造时，默认容量值不同。
hashmap默认数组大小为16，加载因子为0.75,重新hash阈值为12.
hashtable默认数组大小为11,加载因子为0.75，重新hash阈值为8.
6. hashmap和hashtable的数组扩容方式不同。
hashmap中的数组容量大小始终保证为2的指数。重新hash,扩充容量方式为，当前容量大小*2.
hashtable扩充容量方式为：int newcapacity = oldcapacity * 2 + 1;
7. 一些成员方法不同。
hashtable包含一些旧的方法，如contains方法。
面试中常会碰到。
linkedhashmap继承自hashmap并且实现了map接口。和hashmap一样，linkedhashmap允许key和value均为null。
于该数据结构和hashmap一样使用到hash算法，因此它不能保证映射的顺序，尤其是不能保证顺序持久不变（再哈希）。
如果你想在多线程中使用，那么需要使用collections.synchronizedmap方法进行外部同步。
linkedhashmap与hashmap的不同之处在于，linkedhashmap维护着运行于所有条目的双向链接列表，此链接列表可以是插入顺序或者访问顺序。
对于linkedhashmap而言，它继承与hashmap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类hashmap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析linkedhashmap的源代码：
linkedhashmap采用的hash算法和hashmap相同，但是它重新定义了数组中保存的元素entry，该entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：
java代码
1. /**
2. * 双向链表的表头元素。
3. */
4. private transient entry<k,v> header;
5.
6. /**
7. * linkedhashmap的entry元素。
8. * 继承hashmap的entry元素，又保存了其上一个元素before和下一个元素after的引用。
9. */
10.private static class entry<k,v> extends hashmap.entry<k,v> {
11. entry<k,v> before, after;
12. ……
13.}
通过源代码可以看出，在linkedhashmap的构造方法中，实际调用了父类hashmap的相关构造方法来构造一个底层存放的table数组。如：
1. public linkedhashmap(int initialcapacity, float loadfactor) {
2. super(initialcapacity, loadfactor);
3. accessorder = false;
4. }
hashmap中的相关构造方法：
1. public hashmap(int initialcapacity, float loadfactor) {
2. if (initialcapacity < 0)
3. throw new illegalargumentexception("illegal initial capacity: " +
4. initialcapacity);
5. if (initialcapacity > maximum_capacity)
6. initialcapacity = maximum_capacity;
7. if (loadfactor <= 0 || float.isnan(loadfactor))
8. throw new illegalargumentexception("illegal load factor: " +
9. loadfactor);
10.
11. // find a power of 2 >= initialcapacity
12. int capacity = 1;
13. while (capacity < initialcapacity)
14. capacity <<= 1;
15.
16. this.loadfactor = loadfactor;
17. threshold = (int)(capacity * loadfactor);
18. table = new entry[capacity];
19. init();
20.}
我们已经知道linkedhashmap的entry元素继承hashmap的entry，提供了双向链表的功能。在上述hashmap的构造器
中，最后会调用init()方法，进行相关的初始化，这个方法在hashmap的实现中并无意义，只是提供给子类实现相关的初始化调用。
linkedhashmap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素entry的初始化操作。
1. void init() {
2. header = new entry<k,v>(-1, null, null, null);
3. header.before = header.after = header;
linkedhashmap并未重写父类hashmap的put方法，而是重写了父类hashmap的put方法调用的子方法void addentry(int hash, kkey, v value, int bucketindex) 和voidcreateentry(int hash, k key, v value, int bucketindex)，提供了自己特有的双向链接列表的实现。
1. void addentry(int hash, k key, v value, int bucketindex) {
2. // 调用create方法，将新元素以双向链表的的形式加入到映射中。
3. createentry(hash, key, value, bucketindex);
4.
5. // 删除最近最少使用元素的策略定义
6. entry<k,v> eldest = header.after;
7. if (removeeldestentry(eldest)) {
8. removeentryforkey(eldest.key);
9. } else {
10. if (size >= threshold)
11. resize(2 * table.length);
12. }
1. void createentry(int hash, k key, v value, int bucketindex) {
2. hashmap.entry<k,v> old = table[bucketindex];
3. entry<k,v> e = new entry<k,v>(hash, key, value, old);
4. table[bucketindex] = e;
5. // 调用元素的addbrefore方法，将元素加入到哈希、双向链接列表。
6. e.addbefore(header);
7. size++;
8. }
1. private void addbefore(entry<k,v> existingentry) {
2. after = existingentry;
3. before = existingentry.before;
4. before.after = this;
5. after.before = this;
6. }
linkedhashmap重写了父类hashmap的get方法，实际在调用父类getentry()方法取得查找的元素后，再判断当排序模式accessorder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
1. public v get(object key) {
2. // 调用父类hashmap的getentry()方法，取得要查找的元素。
3. entry<k,v> e = (entry<k,v>)getentry(key);
4. if (e == null)
5. return null;
6. // 记录访问顺序。
7. e.recordaccess(this);
8. return e.value;
9. }
1. void recordaccess(hashmap<k,v> m) {
2. linkedhashmap<k,v> lm = (linkedhashmap<k,v>)m;
3. // 如果定义了linkedhashmap的迭代顺序为访问顺序，
4. // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。
5. if (lm.accessorder) {
6. lm.modcount++;
7. remove();
8. addbefore(lm.header);
9. }
10.}
linkedhashmap定义了排序模式accessorder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。
1. private final boolean accessorder;
一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看linkedhashmap的构造方法，如：
1. public linkedhashmap(int initialcapacity,
2. float loadfactor,
3. boolean accessorder) {
4. super(initialcapacity, loadfactor);
5. this.accessorder = accessorder;
该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建lru缓存。linkedhashmap提供了removeeldestentry(map.entry<k,v>eldest)方法，在将新条目插入到映射后，put和 putall将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
1. protected boolean removeeldestentry(map.entry<k,v> eldest) {
2. return false;
3. }
此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建lru缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。
例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。
1. private static final int max_entries = 100;
2. protected boolean removeeldestentry(map.entry eldest) {
3. return size() > max_entries;
1. linkedhashmap继承于hashmap，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序（按从近期访问最少到近期访问最多的顺序）。默认情况下按插入顺序访问，当accessorder设置为true时，按最后访问顺序遍历数据。
2. linkedhashmap非线程安全。
3. linkedhashmap适合做lru缓存。
treemap是一个支持排序的基于红黑树（red-black tree）的<code>navigablemap</code>实现，非线程安全。treemap继承abstractmap,实现navigablemap，navigablemap接口继承sortedmap接口。此实现为 containskey、get、put 和 remove 操作提供受保证的 log(n) 时间开销。
sortedmap提供关于键的总体排序的map。该映射是根据其键的自然顺序进行排序的，或者根据通常在创建有序映射时提供的 comparator 进行排序。对有序映射的 collection 视图（由 entryset、keyset 和 values 方法返回）进行迭代时，此顺序就会反映出来。
插入sortedmap的所有键都必须实现 comparable 接口（或者被指定的比较器接受）。另外，所有这些键都必须是可互相比较的：对有序映射中的任意两个键 k1 和 k2 执行 k1.compareto(k2)（或 comparator.compare(k1, k2)）都不得抛出 classcastexception。试图违反此限制将导致违反规则的方法或者构造方法调用抛出 classcastexception。
所有通用sortedmap实现类都应该提供 4 个“标准”构造方法：
1) void（无参数）构造方法，它创建一个空的有序映射，按照键的自然顺序（实现comparable接口，方法compareto为自然比较方法，按此方法比较大小排序）进行排序。 2) 带有一个 comparator 类型参数的构造方法，它创建一个空的有序映射，根据指定的比较器进行排序。
3) 带有一个 map 类型参数的构造方法，它创建一个新的有序映射，其键-值映射关系与参数相同，按照键的自然顺序进行排序。
4) 带有一个 sortedmap 类型参数的构造方法，它创建一个新的有序映射，其键-值映射关系和排序方法与输入的有序映射相同。无法保证强制实施此建议，因为接口不能包含构造方法。
sortedmap新增了一些成员方法，如下图所示：
navigablemap<k,v>接口，扩展自 sortedmap，具有了针对给定搜索目标返回最接近匹配项的导航方法。方法 lowerentry、floorentry、ceilingentry 和 higherentry 分别返回与小于、小于等于、大于等于、大于给定键的键关联的 map.entry 对象，如果不存在这样的键，则返回 null。类似地，方法 lowerkey、floorkey、ceilingkey 和 higherkey 只返回关联的键。所有这些方法是为查找条目而不是遍历条目而设计的。
将comparator属性赋值为null。如果要控制treemap中元素的存储顺序，应使用带comparator参数的构造器。
先判断root是否为null，如果为null，则创建一个新的entry对象，并赋值给root属性。否则，首先判断是否传入了compatator实现，如果是，则基于红黑树的方式遍历，直到为树节点null，使用传入的comparator比较key的大小，如果找到相等的key则更新其值，若没有找到……，如果comparator为null，则判断key是否为null，如果是null，抛出nullpointerexception，对于key不是null时，取key对于的comparator进行红黑树的遍历和比较，与上述类似。
如果没有找到相同的key，则创建一个新的entry对象，并将其parent设置为上面所寻找到的元素，并根据和parent key比较的情况设置parent的left和right属性。最后对红黑树进行调整。
concurrenthashmap是线程安全的hashmap实现。支持获取，查找时完全并发和更新时可调整并发的哈希表。获取操作（包括 get）通常不会受阻塞。并发场景中(多个线程的情况下) concurrenthashmap比hashmap优秀很多。
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)