javaSE_集合与队列(map)
Map:健值对，健不能重，和set一样，有HashMap、LinkedHashMap、TreeMap三种。
HashMap，基于散列表实现，查找速度快（依赖hashcode()和equals()），存放元素无序。
ConcurrentHashMap，线程安全的HashMap，用于替代HashTable（线程安全，但基于整个对象的锁实现的，效率不高），而ConcurrentHashMap是采用分段加锁的方式实现，提升了效率。
LinkedHashMap，基于散列表、双向链表实现。如HashMap的查找速度，遍历时有序（默认为插入顺序，可通过构造方法设置“最近最少使用(Least Recently Used)顺序”）。
TreeMap，基于红黑树实现，存放有序（依赖Compareable）。
1) HashMap实现原理，如何解决冲突
HashMap使用Hash表，即数组+链表的方式存储数据。
存储时，通过key.hash获取一个hash的数值，再模上hash表的长度，得到key值在hash表中的索引位置。如果此位置为空则直接添加值;如果此位置有值，则将新的key放到此位置上，同时新值对应的Entry的next指向之前的值，即在链表的头部插入数据。
优化：当数据量越来越多，链表就会越来越长，性能也就越差。HashMap里面设置了一个因子，随着Entry的sise越来越大，Entry[]会以一定的规则加长长度。
2) HashTable实现原理
它的每个方法都是synchronized类型，对hashtable的任何操作都会把整个表锁住，因此是线程安全的。当put数据时，会先计算hash值，如果此位置没有元素则直接添加，如d1，如果已有元素，会按照链表的方式将元素插入在链表的头部，如aa。
3) ConcurrentHashMap实现原理
内部使用Segment数组，每个Segment类似于HashTable，操作时是锁住某个Segment对象，其他线程可以并发操作其他Segment对象，因此效率要比HashTable高.
4) hashcode()和equals()
hashcode()和equals()即用于识别对象的身份。
在HashMap或类似的实现中，查找一个对象，是通过hashcode()返回的散列值映射到一个范围内的下标，在通过equals()比较此下标连接的链表是否存在相同的对象。
简单来说，hashcode()用于参考、快速定位（缩减范围），真正是否等于是依赖equals()。
覆盖这两个方法有什么原则呢？
equals()的覆盖，主要是基于此对象的业务。
而hashcode()的覆盖原则，详情可参见《Effective Java》的“覆盖equals时总要覆盖hashcode”一节。
有几个比较重要的原则：
1、两个equals相等的对象，其hashcode是相等的。
2、两个equals不等的对象，其hashcode有可能是相等的。
3、好的hashcode()应产生分布均匀的散列码。
和set一样，map的key值是不能重复的，如果是自定义对象，是通过hashcode和equals来判断是否为同一个对象的，因此如果以对象作为key值，需要注意这两个方法的重载。
5) LinkedHashMap的两种遍历方式
public static void useLinkedHashMap(){
System.out.println("--LinkedHashMap根据输入的顺序输出--");
LinkedHashMap<String, String> linkedHashMap=new LinkedHashMap<>();
linkedHashMap.put("3", "Value3");
linkedHashMap.put("1", "Value1");
linkedHashMap.put("2", "Value2");
linkedHashMap.put("b", "ValueB");
linkedHashMap.put("a", "ValueA");
linkedHashMap.get("2");
linkedHashMap.get("b");
Iterator lit = linkedHashMap.entrySet().iterator();
while (lit.hasNext()) {
Map.Entry e = (Map.Entry) lit.next();
System.out.println(e.getKey() + "--" + e.getValue());
}
System.out.println("--LinkedHashMap最近最少使用排序--");
// 初始容量、加载因子使用默认的16和0.75,排序为true
LinkedHashMap<String, String> Map2 = new LinkedHashMap<>(16, 0.75f, true);
Map2.put("3", "Value3");
Map2.put("1", "Value1");
Map2.put("2", "Value2");
Map2.put("b", "ValueB");
Map2.put("a", "ValueA");
Map2.get("b");
Map2.get("2");
Iterator lit2 = Map2.entrySet().iterator();
while (lit2.hasNext()) {
Map.Entry e = (Map.Entry) lit2.next();
System.out.println(e.getKey() + "--" + e.getValue());
}
}
输出：
--LinkedHashMap根据输入的顺序输出--
3--Value3
1--Value1
2--Value2
b--ValueB
a--ValueA
--LinkedHashMap最近最少使用排序--
3--Value3
1--Value1
a--ValueA
b--ValueB
2--Value2
因为b和2刚使用，因此排在了最后。
6) 自定义对象之HashMap
public static void useCustomObjMap(){
System.out.println("--HashMap使用自定义对象--");
Map<Student, String> map = new HashMap<>();
map.put(new Student("张三", 30), "1");
map.put(new Student("李四", 32), "2");
map.put(new Student("王五", 31), "3");
map.put(new Student("李四", 33), "4");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()){
Map.Entry e = (Entry) iter.next();
Student st = (Student) e.getKey();
System.out.println(st.getName() + "--" + e.getValue());
}
}
输出：
--treeMap使用自定义对象--
王五--3
李四--2
李四--4
张三--1
可见，有两个李四，虽然姓名一样，但是这是两个对象，因此可以重复。
如果重载student的hashcode和equals方法，以姓名为判断两对象是否相同的依据：
public class Student {
private String name;
private Integer age;
public Student(String name, Integer age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
输出：
--HashMap使用自定义对象--
王五--3
李四--4
张三--1
结论：hashMap如果以自定义对象为key值，需要注意其hashcode和equals。
7) 自定义对象之TreeMap
将上面的hashMap改为TreeMap，运行时直接报错：
public static void useCustomObjMap(){
System.out.println("--TreeMap使用自定义对象--");
Map<Student, String> map = new TreeMap<>();
map.put(new Student("张三", 30), "1");
map.put(new Student("李四", 32), "2");
map.put(new Student("王五", 31), "3");
map.put(new Student("李四", 33), "4");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()){
Map.Entry e = (Entry) iter.next();
Student st = (Student) e.getKey();
System.out.println(st.getName() + "--" + e.getValue());
}
}
Exception in thread "main" java.lang.ClassCastException: com.gary.set.Student cannot be cast to java.lang.Comparable
说student类需要重载Comparable。
public class Student implements Comparable{
private String name;
private Integer age;
public Student(String name, Integer age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public int compareTo(Object arg0) {
Student st = (Student) arg0;
return this.name.hashCode() - st.name.hashCode();
}
}
此时输出：
--TreeMap使用自定义对象--
张三--1
李四--4
王五--3
结论：TreeMap使用自定义对象为key值，其类需要重载Comparable。
8) Map的遍历
有四种方法遍历：
public static void traverseMap(){
HashMap<String, String> hashMap=new HashMap<>();
hashMap.put("3", "Value3");
hashMap.put("1", "Value1");
hashMap.put("2", "Value2");
hashMap.put("b", "ValueB");
hashMap.put("a", "ValueA");
// 方法一
System.out.println("------entrySet------");
for (Map.Entry<String, String> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + "--" + entry.getValue());
}
// 方法二：此方法比entrySet快10%
// 遍历key
System.out.println("------keySet------");
for (String key : hashMap.keySet()){
System.out.println(key);
}
// 遍历值
System.out.println("------values------");
for (String value : hashMap.values()){
System.out.println(value);
}
// 方法三
// 性能和keySet的性能差不多，而且可以在循环体中调用it.remove来删除数据，上面的则不能
System.out.println("------iterator------");
Iterator it = hashMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry e = (Map.Entry) it.next();
System.out.println(e.getKey() + "--" + e.getValue());
}
// 方法四
// 每次使用get方法取值是相当慢的
System.out.println("------keySet get------");
for (String key : hashMap.keySet()){
System.out.println(key + "--" + hashMap.get(key));
}
}
综上所述，方法三使用iterator是最好的选择，速度快，而且还可以执行删除操作。