映射表是一种数据结构，用于存放键值对。如果提供了键，就能查找到值。
Map接口的方法：
void
clear() Removes all of the mappings from this map (optional operation).
boolean
containsKey(Object key) Returns true if this map contains a mapping for the specified key.
boolean
containsValue(Object value) Returns true if this map maps one or more keys to the specified value.
Set<Map.Entry<K,V>>
entrySet() Returns a Set view of the mappings contained in this map.
boolean
equals(Object o) Compares the specified object with this map for equality.
V
get(Object key) Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
int
hashCode() Returns the hash code value for this map.
boolean
isEmpty() Returns true if this map contains no key-value mappings.
Set<K>
keySet() Returns a Set view of the keys contained in this map.
V
put(K key, V value) Associates the specified value with the specified key in this map (optional operation).
void
putAll(Map<? extends K,? extends V> m) Copies all of the mappings from the specified map to this map (optional operation).
V
remove(Object key) Removes the mapping for a key from this map if it is present (optional operation).
int
size() Returns the number of key-value mappings in this map.
Collection<V>
values() Returns a Collection view of the values contained in this map.
Java类库为映射表提供了两个通用的实现：HashMap（对键进行散列）和TreeMap（用键的整体顺序对元素排序，并将其组织成搜索树），这两个类都实现了Map接口。
HashMap比TreeMap更快，但没有排序功能。下面重点介绍HashMap：
HashMap
散列表（HashMap）和散列集（HashSet）都是散列表这种数据结构。
散列表（Hash Table）
散列表由链表数组实现，每个列表成为一个桶（bucket），一个桶就是一个链表。如下图所示，该图有16个桶。根据关键字的散列码（HashCode）与桶的总数取余得到元素的位置。图中，0~15代表桶的标号，而右边一些数字代表关键字的散列码。下面这个散列表，其中4个空间被使用，即36%的空间已经被使用。而散列表的装填因子（load factor）默认为0.75，即当75%的空间已经被使用时进行再散列（rehashed），桶的总数变成双倍。注意：如果未设定，桶的总数的初始默认值为16。
这里主要讨论HashMap：
散列映射表（HashMap）仅仅是根据关键字的散列码（HashCode）来得到元素要存放在哪条链表上，而判断两个对象是否相等是根据对象的equals方法确定的。如果想将Employee类的某个对象添加到HashMap中，首先要调用这个对象（Value）所对应的键（Key）的hashCode方法计算键的散列码，然后与桶的总数取余的到这个键值对的桶的索引。如果返回的散列码与HashMap中已经存在的某个键的散列码相同，则第二个值就会取代第一个值。因为
键必须是唯一的，不能对同一个键存放两个值。也就是说，散列映射表中，value完全是key的附属，一点也不会影响存储。
HashMap存储在bucket中的是entry（条目）的引用，一个bucket其实就是一条entry链表。entry是一种数据结构，里面包含了key，value，next等实例域，其中next指的是下一个引用的位置，如果next == null，则表示这条entry链结束了。HashMap在执行add操作的时候，总是把最新的元素添加到bucket中entry链表的头部，再将这个最新元素的next指向旧链表，所以最早加入的元素一定在链表末尾。
其他的知识一定要读一读这篇文章：java中HashMap详解
这里附加一道OCJP的题目来增强理解：
Given
2
3
4
5
6
7
8
9
10
2 private name;
3 public Person(String name) {
4 this.name = name;
5 }
6 public int hashCode() {
7 return 420;
8 }
9 }
10
2
2
A. The time to find the value from HashMap with a Person key depends on the
size of the map.
B. Deleting a Person key from a HashMap will delete all map entries for all keys of type Person.
C. Inserting a second Person object into a HashSet will cause the first Person object to be
removed as a duplicate.
D. The time to determine whether a Person object is contained in a HashSet is constant and does NOT
depend on the size of the map.
Answer: A
下面来解释一下：
红色为翻译
B选项：
删除HashMap中一个Person对象对应的键将会删除这个散列映射表中Person类的全部条目。错误，HashMap中Person对象的键值不是由Person对象决定的，而是程序给定的键，例如staff.add("123-345", bob)，就是把键为123-456的bob对象添加到名为staff的HashMap中，因而HashMap允许添加相同的对象。所以说，删除一个键对应的Person对象并不会删除所有的条目，他们的key都不同嘛。
C选项：
向HashSet中插入另外一个Person对象将会引起第二个对象覆盖第一个对象。错误，虽然Person对象的hashCode方法返回的值都是420，这仅仅表明两个Person对象在一个entry链表中，接下来要调用equals方法，由于Person类没有equals方法，所以调用Object的equals方法返回对象的存储地址，很明显两个Person对象的存储地址是不同的。综上，HashSet中可以添加不同的Person对象，只要equals方法返回值不同就好。
D选项：
判断一个HashSet中是否存在一个Person对象的次数是常数次，和map的大小无关。错误，由于Person对象的hashCode返回的值都是420，所以HashSet中的Person对象都在一个bucket中，组成了一条entry链表，查询速度与entry链表的大小息息相关。
A：选项：
由key来查找value的次数与map的大小有关。正确，map越大，即bucket的个数越多，entry链的长度相应的来说就越小（hashcode和桶个数取余后的数一样的几率就越小）。
另外，要注意的是HashMap有三个重要的视图：
- Set<K> keySet();
- Collection<K> values();
- Set<Map.Entry<K,V>> entrySet();
其中第一个方法和第三个方法返回的是一个集（Set），而第二个方法返回的是一个集合（Collection）。
以下例子利用了HashMap的一些重要的方法：
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
2
3import java.util.HashMap;
4import java.util.Map;
5import java.util.Set;
6
7public class Test{
8 public static void main(String...arg){
9 Map<String, Employee> staff = new HashMap<String, Employee>();
10 Employee lily = new Employee("Lily", 4000);
11 Employee john = new Employee("John", 6000);
12 staff.put("1234-9876", lily);
13 staff.put("345-8765", john);
14
15 Employee e = staff.get("345-8765");
16 System.out.println(e.getName());//John
17
18 System.out.println(staff.containsKey("1234-9876"));//true
19 System.out.println(staff.containsValue(lily));//true
20 System.out.println(staff.size());//2
21
22 //键集
23 Set<String> myKeySet = staff.keySet();
24 for(String myKey: myKeySet){
25 System.out.println(myKey);
26 }
27 /*结果：
28 * 345-8765
29 * 1234-9876
30 */
31
32
33 //值集合（不是集set）
34 //staff.values()返回类型为Collection<Employee>
35 for(Employee myEmployee : staff.values()){
36 System.out.println(myEmployee);
37 }
38 /*结果：
39 * id:2,name:John,salary:6000.0
40 * id:1,name:Lily,salary:4000.0
41 * */
42
43
44 //键值对集
45 //staff.entrySet()返回类型为Set<Entry<String, Employee>>
46 for(Map.Entry<String, Employee> entry: staff.entrySet()){
47 String key = entry.getKey();
48 Employee value = entry.getValue();
49 System.out.println("key: " + key + "\nvalue: " + value);
50 }
51 /*结果：
52 * key: 345-8765
53 * value: id:2,name:John,salary:6000.0
54 * key: 1234-9876
55 * value: id:1,name:Lily,salary:4000.0
56 * */
57
58 staff.remove("345-8765");
59 System.out.println(staff.size());//1
60
61 //putAll方法，
62 Map<String, Manager> otherStaff = new HashMap<String, Manager>();
63 Manager jim = new Manager("Jim", 6000, 1000);
64 Manager gin = new Manager("Gin", 8000, 2000);
65 otherStaff.put("1111-2222", jim);
66 otherStaff.put("2222-3333", gin);
67
68 staff.putAll(otherStaff);
69 for(Map.Entry<String, Employee> entry: staff.entrySet()){
70 String key = entry.getKey();
71 Employee value = entry.getValue();
72 System.out.println("key: " + key + "\nvalue: " + value);
73 }
74 /*结果：
75 * key: 1111-2222
76 * value: id:3,name:Jim,salary:6000.0,bonus:1000.0
77 * key: 2222-3333
78 * value: id:4,name:Gin,salary:8000.0,bonus:2000.0
79 * key: 1234-9876
80 * value: id:1,name:Lily,salary:4000.0
81 * */
82 }
83}
84
85class Employee{
86 public Employee(String name){
87 this.name = name;
88 id = nextId;
89 nextId++;
90 }
91
92 public String toString(){
93 return "id:" + id + ",name:" + name +",salary:" + salary;
94 }
95
96 public Employee(String name, double salary){
97 this(name);//调用另一构造器
98 this.salary = salary;
99 }
100
101 //定义访问器方法
102 public final String getName(){
103 return name;
104 }
105
106 public double getSalary(){
107 return salary;
108 }
109
110 public final int getId(){
111 return id;
112 }
113
114
115 //定义更改器方法
116 public final void setName(String name){
117 this.name = name;
118 }
119
120 public final void setSalary(double salary){
121 this.salary = salary;
122 }
123
124 public final void raiseSalary(double percent){
125 this.salary *= (1 + percent);
126 }
127
128 //定义变量
129 private String name = "";//实例域初始化
130 private double salary;
131 private int id;
132 private static int nextId = 1;
133
134}
135
136class Manager extends Employee{
137 public Manager(String name, double salary, double bonus){
138 super(name, salary);//super在构造器中的使用，可以调用超类的构造器
139 setBonus(bonus);
140 }
141
142 public String toString(){
143 return super.toString() + ",bonus:" + bonus;
144 }
145
146 public double getBonus(){
147 return bonus;
148 }
149
150 //重写getSalary方法
151 public double getSalary(){
152 double baseSalary = super.getSalary();//调用了超类的getSalary方法
153 return baseSalary + bonus;
154 }
155
156 public void setBonus(double bonus){
157 this.bonus = bonus;
158 }
159
160 private double bonus;
161}
162
