JAVA_map总结
标签:removenewhashtableversionmovebool简单ret介绍
map,键值对的集合,由于和pojo的结构和map类似,经常相互转换,或者作为带有特定标识的数据的集合存储方式二使用。
还是先放结论:
类型
数据结构
特点描述
HashMap
散列表(拉链法)
最常用,无序,线程不安全
Hashtable
散列表(拉链法)
无序,线程安全
LinkedHashMap
双向链表+散列表(拉链法)
有序(插入顺),线程不安全
WeakHashMap
散列表(拉链法)
无序,线程不安全,弱引用键,保存对象被回收时,自动删除
TreeMap
红黑树
有序(自动排序),线程不安全
基本概念,何为哈希?
先扔个概念摘自百度百科,哈希:
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
关于散列表:
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
拉链法:
拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1
嗯,看了觉得很迷糊对吧,那么来一步步的说。
嗯,干巴巴的说果然还是很难理解,那么,现在有以下数据,要用散列表(拉链法)的方式进行存储,结果会是这么样的呢?
数据:
{\”aa\”,\”1\”},{\”ab\”,\”2\”},{\”bA\”,\”3\”},{\”bB\”,\”4\”},{\”bC\”,\”5\”}
顺便,在jdk1.8.0_121中,对String对象的哈希算法如下:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
则计算以上数据key值得哈希值分别为: 3104,3105,3103,3104,3105
于是使用数组存储的话,大体是这么个印象
数组[3103] = {\”bA\”,\”3\”}
数组[3104] = {\”aa\”,\”1\”},{\”bB\”,\”4\”}
数组[3105] = {\”ab\”,\”2\”},{\”bC\”,\”5\”}
由于存在哈希值相同的情况,所以需要使用拉链法进行。由于要在数组同一位置存多个数据,采用单链的方式的话,需要记录链表下一个,next的值,所以需要包装一下。结果的话,大体是这种效果:
数组(3103) -> {\”bA\”,\”3\”}
数组(3104) -> {\”aa\”,\”1\”} -> {\”bB\”,\”4\”}
数组(3105) -> {\”ab\”,\”2\”} -> {\”bC\”,\”5\”}
HashMap
经过以上说明,基本已经对hash有了概念的话,接下来就方便了。
还是上源码(jdk1.8.0_121,java.util.HashMap):
transient Node
static class Node
Node(int hash, K key, V value, Node<K,V> next) {……}
public final K getKey() {……}
public final V getValue() {……}
public final String toString() {……}
public final int hashCode() {……}
public final V setValue(V newValue) {……}
public final boolean equals(Object o) {……}