/ 学习笔记  

Hash-Map-HashMap

在平时coding时虽然经常会用到HashMap,但没有仔细思考它的实现原理,也常常将HashTableHashMapTreeMap等概念特性混淆,最主要原因是不太理解它们的底层逻辑,后面仔细思考了一下,发现自己竟然分不太清Hash和Map,后面查了一些资料,总算是弄明白了一些,记录一下。

Hash是啥?

Hash又称散列,它表示的是通过一个输入值,通过装换算法输出一个对应的值,这个装换算法是一种映射关系,又叫做Hash函数,hash函数能够使对一个数据的访问过程更加有效,通过hash函数,数据元素可以快速的被定位。hash算法也并不是唯一的,在不同的应用中有不同的hash算法,比如常见的的FNK算法,CRC系列算法,MD5SHA-1等。

HashTable是啥?

HashTable是hash函数的一个主要应用,使用散列表能够快速的查找数据记录,是一种可以根据键值对直接访问的数据结构,它通过把关键码映射到表中的一个位置来访问记录,从而加快了查找的速度,HashTable是数组和链表的结合,使用Hash函数将被查找的键转化为数组的索引,然后根据索引就可以定位到数据记录,当然在进行转化时会发生hash冲突,如果单桶存储的数据条目过多,将会导致性能下降,这时候就需要考虑是否要使用rehash方法进行扩容了。

Map是啥?

Map是一种关联容器,它提供了一对一的数据处理能力,这与上面所述的hash好像是一个东西,但其实并非这样,在网上也很难找到这两者的具体定义和区别,我个人理解的是Hash更强调的是一种算法,而Map则是一种数据结构(容器),维基百科中是这样定义Map的:

map:In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

在C++的STL中Map是一个标准容器,在Java中Map是定义的一个接口,我们常用的HashMapLinkedHashMap都实现了该接口。

HashMap是啥?

HashMap存储数据采用的是散列表结构(数组+链表的结构),在JDK8中HashMap的底层数据结构已经变为数组+链表+红黑树的结构,这主要原因是为了减少之前提到的hash冲突带来的影响。

HashMap的基本原理是散列表+拉链法,就是在往HashMap中put元素时,会先根据key的hash值得到这个元素在数组中的位置(即下标),然后把这个元素放到对应的位置中。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。

实际情况下,我们希望HashMap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素是我们想要元素,而不用再去遍历链表。最容易的做法就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是“模”运算的消耗是比较大的,在Java中选择了另外一种更快速,消耗更小的方式:首先算得key得hashcode值,然后跟数组的长度-1做一次“与”运算(&)

1
2
3
static int indexFor(int h, int length) {
return h & (length-1);
}

HashMap中get()方法的执行过程是:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。所以hashcodeequals方法是找到对应元素的两个关键方法,通过改写key对象的equalshashcode方法,我们就可以将任意的业务对象作为map的key。在判断两个对象是否真的相等时,必须保证它们的hashcode相同,且保证调用 equals()方法返回true。

TreeMap是啥?

TreeMap在存储数据时是安装特定顺序存储的,并非像HashMap那样无明显顺序,最主要的原因是其底层原理不同,TreeMap的本质是红黑树,红黑树理解起来是比较复杂的,在此就不做展开了。

补充1:HashMap扩容

在JDK7中,HashMap数据结构是数组+链表的方式,HashMap内存储数据的Entry数组默认是16,如果没有对Entry扩容机制的话,当存储的数据一多,Entry内部的链表会很长,这就失去了HashMap的存储意义了,所以HasnMap内部有扩容机制来进行处理。

HashMap内部有:变量size,记录HashMap的底层数组中已用槽的数量;变量threshold,它是HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子);变量DEFAULT_LOAD_FACTOR = 0.75f,默认加载因子为0.75。

HashMap扩容的条件是:当size大于threshold时,对HashMap进行扩容。

1
2
3
4
5
6
7
8
9
//举个例子假如现在有三个元素(3,5,7)要放入map里面,table的的容量是2,如下
[0]=null
[1]=3->5->7

//现在将table的大小扩容成4,分布如下:
[0]=null
[1]=5->7
[2]=null
[3]=3

在JDK8里面,HashMap的底层数据结构已经变为数组+链表+红黑树的结构了,因为在hash冲突严重的情况下,链表的查询效率是O(n),所以JDK8做了优化对于单个链表的个数大于8的链表,会直接转为红黑树结构算是以空间换时间,这样以来查询的效率就变为O(logN)。

简单总结就是,JDK7里面是先判断table的存储元素的数量是否超过当前的threshold=table.length*loadFactor(默认0.75),如果超过就先扩容,在JDK8里面是先插入数据,插入之后在判断下一次++size的大小是否会超过当前的阈值,如果超过就扩容。

补充2:区别Collection和Map

Collection 和Map 是Java容器类库的两种主要类型,最主要的区别在于Collection保存的是单个元素,而Map保存的是一个键值对。

下面例子展示了一些基本类型的容器,第一个 fill() 可以用于所用类型的Collection,这些类型都实现了用来添加新元素的 add() 方法。而第二个 fill() 使用与Map,它们都实现了添加键值对的 put() 方法。

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
import java.util.*;
// 容器的打印
public class PrintingContainers {

static Collection fill(Collection<String> collection){
collection.add("rat");
collection.add("cat");
collection.add("dog");
collection.add("dog");

return collection;
}

static Map fill(Map<String, String> map){
map.put("rat", "Fuzzy");
map.put("cat", "Rags");
map.put("dog", "Bosco");
map.put("dog", "Spot");

return map;
}


public static void main(String args[]){
// List 类型
System.out.println(fill(new ArrayList<String>()));
System.out.println(fill(new LinkedList<String>()));

// Set 类型
System.out.println(fill(new HashSet<String>()));
System.out.println(fill(new TreeSet<String>()));
System.out.println(fill(new LinkedHashSet<String>()));

// Map 类型
System.out.println(fill(new HashMap<String, String>()));
System.out.println(fill(new TreeMap<String, String>()));
System.out.println(fill(new LinkedHashMap<String, String>()));

}
}

ArrayListLinkedList 都是List类型,都是按照插入了顺序保存元素,ArrayList可以理解为动态数组,LinkedList可以理解为链表,两者最主要的区别在于执行某些类型的操作时的性能。

HashSetTreeSetLinkedHashSet都是Set类型,在Set类型中每个元素只不留一次,不会出现相同的项,它们的一个主要区别是存储元素的方式不同,HashSet是以散列的形式保存元素,所以是无序的,而TreeSet是以树的形式存储数据,是按照一定的顺序要求保存的。而LinkedHashSet则是按照添加的顺序保存对象的。

HashMapTreeMapLinkedHashMap都是Map类型,保存都是键值对(key—value),HashMap没有按照任何明显的顺序来保存其元素,但查找效率是比较快的,它有自己的算法来控制顺序,TreeMap则是按照某种特定顺序来保存键的,LinkedHashMap则是按照插入顺序保存键,并且保存了HashMap的查询速度。

Tips:

1、越底层的东西越复杂,当然也越有用!2、专业的书比网上的资料更全面更详细。3、好奇心和求知欲是第一驱动力。