HashMap的一些理解

# Map

## 什么是Map

Map 翻译为 映射

1. Map是接口，在java.util包

2. Java 中提供的面向“查询”的API
- 查询中输入的被检索信息称为 “Key”，key翻译为关键信息
- 查询结果称为“Value”， Value 翻译为“值”

- Map提供了根据Key查询Value的功能

3. Map接口有两个常用实现类
- 最重要的实现类 HashMap，Hash 散列，HashMap也称为散列表，哈希表
- HashMap是查询**最快**的 API

- TreeMap 采用二叉树算法。 相当于2分查找，速度很快。

4. Map 中key不允许重复，Value可以重复

5. 尽量将软件中的查找功能用Map进行优化！提高软件的性能。


## 使用Map


1. 创建map对象，是空的，没有数据。

Map map = new HashMap();

2. 将被查询的 Key-Value 成对的存储到map


Object obj = map.put(key, value);

> 如果第一次put，返回null，如果第二次put同样的key，返回被替换的对象


3. 查询时候，根据Key查询到Value


value = map.get(key);


> 如果没有找到返回null


案例： 使用put方法：


public class MapPutDemo {

public static void main(String[] args) {
/*
* 将数据添加到Map中
*/
Map map = new HashMap();
//第一次将“u1”-"Tom"添加到到map
Object obj = map.put("u1", "Tom");
//第一次返回null
System.out.println(obj);
//第二次将“u1”的value替换为Jerry
obj = map.put("u1", "Jerry");
//返回被替换的Tom
System.out.println(obj);
//显示Map中的内容 ？思考如下输出用了那个方法
System.out.println(map); //toString()

/*
* 利用泛型定义类型安全的map集合 
*/
Map map2=
new HashMap<>();
//Java 6 中不能省略
//Map map3=
// new HashMap();
String s = map2.put("u1", "Tom");
System.out.println(s);
s = map2.put("u1", "Jerry");
System.out.println(s);
System.out.println(map2); 

}
}


案例: 使用get方法


public class MapGetDemo {

public static void main(String[] args) {
/*
* 测试map的查询方法get
* 1. 如果找到就返回key对应的值
* 2. 如果没有找到返回 null
*/
Map map=
new HashMap<>();
//向map中添加数据
map.put("u1", "Tom");
map.put("u2", "Jerry");
//从map中检索
String v1 = map.get("u1");
String v2 = map.get("u3");
System.out.println(v1);
System.out.println(v2);//null
}

}

## HashMap查询性能优异


案例： 比较HashMap查询性能：


public class MapTestDemo {
public static void main(String[] args) {
/*
* 纵向比较 map 的查询性能
*/
test(1000);
test(10000);
test(100000);
/*
* 横向对比 HashMap和LinkedList的查询性能 
*/
testLinkedList(10000);
testLinkedList(100000);
}
/**
* 测试LinkedList的查找性能
* LinkedList 采用双向循环链表结构，
* 它的头尾查询性能好，中部查找性能差
*/
public static void testLinkedList(int n){
LinkedList list=
new LinkedList<>();
for(int i=0; i list.add("u"+i);
}
//从LinkedList中部查询数据
long t1=System.nanoTime();
String str = list.get(n/2);
long t2=System.nanoTime();
System.out.println(str);
System.out.println(t2-t1);
}

/**
* 性能测试方法
*/
public static void test(int n){
Map map=
new HashMap<>();
for(int i=0; i //i=0 1 2 ... n-1
String val = "n"+i;
map.put(i, val);
}
//nanoTime() 返回系统纳秒数1ms=1000000ns
long t1 = System.nanoTime();
String v = map.get(n-1);
long t2 = System.nanoTime();
System.out.println(v); 
System.out.println(t2-t1);
}
}


## Map 的API方法


0. get() 在map中根据key查询得到指定的value
1. size() 检测map集合中元素的个数
2. isEmpty() 检测map集合是否为空
3. remove() 删除map集合中的指定元素，返回被删除的value
4. clear() 清空map集合
5. containsKey() 检测map集合中是否包含指定的key


案例：

public class MapRemoveDemo {

public static void main(String[] args) {
/*
* 演示Map的方法
* size() 集合中元素的数量
* isEmpty() 检测集合是否为空
* remove()  删除集合中的元素
*/
Map map=
new HashMap<>();
System.out.println(map.size());
System.out.println(map.isEmpty()); 
map.put("u1", "Tom");
map.put("u2", "Jerry");
map.put("u3", "Andy");
map.put("u4", "John");
System.out.println(map.size());
System.out.println(map.isEmpty());
//从map中删除u1元素，返回被删除的value
String val = map.remove("u1");
System.out.println(val);
System.out.println(map.size());
System.out.println(map.isEmpty()); 
//清空map集合的内容
map.clear();
System.out.println(map.size());//0
System.out.println(map.isEmpty());//true
}
}




## HashMap 的工作原理


1. HashMap内部利用数组存储数据。
2. 根据key的hashCode值计算出数组的下标位置，进行添加或者查询数据。
- 根据hashCode计算出数组的下标位置的算法称为“散列算法”
3. 数组下标位置会重复，重复时候利用链表存储重复元素
- 这个链表称为 “散列桶” 
4. 添加和查询时候如果有散列桶，则根据equals方法逐个比较找到位置。


> 由于利用hashCode直接定位到数组的存储位置，无需依次查找，所以HashMap具有极高查找性能。




影响HashMap的查找性能因素：


1. 如果数据多，而数组容量少，大量数据重复的存储在散列桶中，造成在散列桶中进程大量的顺序查找，性能差。 
- 解决办法是提供更多数组容量，减少散列桶中重复的数据。
- 如果保持 元素的总数和数组容量的比值少于 75% 时候，出现重复位置的情况少于3个！
- HashMap中默认的“加载因子” 就是75%, HashMap中添加元素时候，HashMap始终会保持元素和数组容量的比值小于75%，如果超过75%则进行数组扩容“重新散列”


2. hashCode 方法
- Java 在 Object类上定义了hashCode方法，用于支持HashMap中的算法。
- 作为key的类型必须很好的实现 hashCode方法，否则会影响HashMap性能
- 当两个对象 equals方法比较结果为true时候，他们的hashCode相同
- 当两个对象 equals方法比较结果为false时候，他们的hashCode近可能不同！


3. equals 方法
- HashMap添加或查找时候，先根据hashCode计算数组下标位置，然后在利用equals比较key对象是否相同。
- 如果key的hashCode和equals方法不"一致", 会造成HashMap工作异常！可能重复添加或者查找不到数据。

> 建议：一定成对重写key的equals方法和hashCode方法。


> java 中的 API String，Integer 等都成对的重写了equals和hashCode。


4. 创建HashMap的性能优化参数
- new HashMap(数组容量，加载因子)
- 默认 new HashMap() 等价于 new HashMap(16, 0.75f)
- 在添加到12个元素以后进行扩容。
- 如果事先可以预测添加到HashMap中数量，则可以声明足够的大的容量，避免反复扩容浪费时间。
- 如果有 1000 条数据需要添加到HashMap，则new HashMap(1500)  


一个有故障的案例:


public class MapHashCodeDemo {
public static void main(String[] args) {
/*
* 作为key的类，如果不很好的重写equals 和
* hashCode方法会造成 HashMap工作故障
*/
HashMap map=
new HashMap<>();
map.put(new Player(1), "吃鸡");
map.put(new Player(2), "英雄联盟");
map.put(new Player(3), "英雄联盟");
Player One= new Player(1);
String game=map.get(one);
System.out.println(game); 
}
}
class Player{
int id;
public Player(int id) {
this.id = id;
}

}


添加 hashCode和equals解决故障：


public class MapHashCodeDemo {
public static void main(String[] args) {
/*
* 作为key的类，如果不很好的重写equals 和
* hashCode方法会造成 HashMap工作故障
*/
HashMap map=
new HashMap<>();
map.put(new Player(1), "吃鸡");
map.put(new Player(2), "英雄联盟");
map.put(new Player(3), "英雄联盟");
Player One= new Player(1);
String game=map.get(one);
System.out.println(game); 
}
}
class Player{
int id;
public Player(int id) {
this.id = id;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Player other = (Player) obj;
if (id != other.id)
return false;
return true;
}

}



## Map 的遍历（迭代）



public class MapEnrtySetDemo {

public static void main(String[] args) {
/*
* 利用EntrySet对map集合进行遍历
*/
Map map=
new HashMap<>();
//如下数据相当于从浏览器收到的请求头
map.put("Host", "doc.tedu.cn");
map.put("Connection", "keep-alive");
map.put("Cache-Control", "max-age=0");
//...
//遍历全部的请求头
//map 没有提供之间遍历的方法！
//可以利用 entrySet 和 keySet 间接实现遍历
// Entry 对象就代表map中的key-value对
// 一个Entry 对象中包含两个属性，一个是key
// 一个是Value，Entry的实现类是HashMap内部类
Set> set = 
map.entrySet();
//set 中包含map中全部的key-value对
//只要遍历 set 就相当于遍历了map
for(Entry e: set){
System.out.println(
e.getKey()+", "+e.getValue());
}
}

}