首先HasMap在JDK 1.7 和 1.8是稍有不同的。
简介
HashMap是一个散列桶（数组和链表,1.8还有红黑树），它存储的内容是键值对(key-value)映射
HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组
了解hashCode和equals
就是hashCode是用于查找使用的，而equals是用于比较两个对象的是否相等的
1.hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址
2.如果两个对象相同，就是适用于equals方法，那么这两个对象的hashCode一定要相同
3.如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点
4.两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里“
HashMap构造函数
HashMap有4个构造函数
参数说明
初始容量
初始容量表示哈希表中桶（数组长度）的数量
负载因子
它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高。如果加载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果加载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认加载因子为0.75，一般情况下我们是无需修改的。
// ********1.无参构造方法
// // 构造一个空的HashMap，初始容量为16，负载因子为0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//HashMap<String, Integer> myHashMap = new HashMap<>();
// ********2.构造一个空的初始容量为initialCapacity，负载因子为0.75的空的HashMap其实它就是调用下面的第三个构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//HashMap<String, Integer> myHashMap = new HashMap<>(10);
// ********3.构造一个空的初始容量为initialCapacity，负载因子为loadFactor的HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//其中最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
tableSizeFor()的主要功能是返回一个比给定整数大且最接近的2的幂次方整数，如给定10，返回2的4次方16.看下面
//HashMap<String, Integer> myHashMap = new HashMap<>(16,0.75f);
// ********4构造一个和指定Map有相同mappings的HashMap，初始容量能充足的容下指定的Map,负载因子为0.75
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//例子
//Map myMap = new HashMap<String,Integer>();
//HashMap<String, Integer> thisMap = new HashMap<>(myMap);
tableSizeFor()实现的源码
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor以输入10为例
tableSizeFor示例图
注意
1.当输入为0的时候，方法的输出为1。
（因为计算机中数字是由补码存储的，-1的补码是 0xffffffff。所以无符号右移之后再进行或运算之后还是 -1。）
2.n = n - 1; 是为了防止输入已经是2的幂次的数，不减1的话，得到结果就会扩大
HashMap的重要的成员变量
1.实际存储key，value的数组，只不过key，value被封装成Node了,第一次使用的时候被初始化，根据需要可以重新分配长度。分配的长度总是2的幂
transient Node<K,V>[] table;
2.平衡因子，上面有说一下的
final float loadFactor;
3.阈值（当前数组长度乘以加载因子的值）。因为 tableSizeFor(int) 返回值给了threshold.当需要resize时的阈值。即当HashMap中KV映射的数量（即size）超过了threshold就会resize。threshold=capacity*loadFactor。
int threshold;
4.当被调用entrySet时被赋值。通过keySet()方法可以得到map key的集合，通过values方法可以得到map value的集合。
transient Set<Map.Entry<K,V>> entrySet;
5.存放在map中的KV映射的总数。
transient int size;
6.HashMap被结构性修改的次数。（结构性修改是指改变了KV映射数量的操作或者修改了HashMap的内部结构（如 rehash）。这个用于fail-fast（快速失败）。
transient int modCount;
7.将链表转换为红黑树的长度TREEIFY_THRESHOLD 和红黑树转回链表的长度UNTREEIFY_THRESHOLD
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
fail-fast（快速失败）:在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历
HashMap的数据结构图jdk1.8
HashMap put方法jdk1.8
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table为空或者长度为0，则resize()
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//确定插入table的位置，算法是(n - 1) & hash，在n为2的幂时，相当于取摸操作。
//找到key值对应的槽并且是第一个，直接加入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//在table的i位置发生碰撞，有两种情况，1、key值是一样的，替换value值，
//2、key值不一样的有两种处理方式：2.1、存储在i位置的链表；2.2、存储在红黑树中
else {
Node<K,V> e; K k;
//第一个node的hash值即为要加入元素的hash
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.2
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//2.1
else {
//不是TreeNode,即为链表,遍历链表
for (int binCount = 0; ; ++binCount) {
///链表的尾端也没有找到key值相同的节点，则生成一个新的Node,
//并且判断链表的节点个数是不是到达转换成红黑树的上界达到，则转换成红黑树。
if ((e = p.next) == null) {
// 创建链表节点并插入尾部
p.next = newNode(hash, key, value, null);
////超过了链表的设置长度8就转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不为空就替换旧的oldValue值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
注：hash 冲突发生的几种情况：
1.两节点key 值相同（hash值一定相同），导致冲突；
2.两节点key 值不同，由于 hash 函数的局限性导致hash 值相同，冲突；
3.两节点key 值不同，hash 值不同，但 hash 值对数组长度取模后相同，冲突；
1.7和1.8的HashMap的不同点
①JDK1.7用的是头插法，而JDK1.8及使用是尾插法，因为JDK1.7是用单链表进行的纵向延伸，当采用头插法就是能够提高插入的效率，但是也会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。
②扩容后数据存储位置的计算方式也不一样：
在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（与运算）（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1） 。
而在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。
其中hash值的计算不想去研究，网上总结说JDK1.7用了9次扰动处理=4次位运算+5次异或，而JDK1.8只用了2次扰动处理=1次位运算+1次异或。
③JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（N）变成O（logN）提高了效率）。
HashMap为什么是线程不安全的？
HashMap 在并发时可能出现的问题主要是两方面：
①put的时候导致的多线程数据不一致
比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的 hash桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
②resize而引起死循环
这种情况发生在HashMap自动扩容时，当2个线程同时检测到元素个数超过数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize()，两个线程同时修改一个链表结构会产生一个循环链表（JDK1.7中，会出现resize前后元素顺序倒置的情况）。接下来再想通过get()获取某一个元素，就会出现死循环。
HashMap和HashTable的区别
主要的区别有：线程安全性，同步(synchronization)，以及速度。
1.HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行
2.HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。
3.另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
4.由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
5.HashMap不能保证随着时间的推移Map中的元素次序是不变的。(红黑树呀)
HashMap例子
键Student类型（自定义类型），值String类型
注意
这里就要想一下自定义对象Student作为键时，什么叫同一个键？
假定要求Student的成员变量值都相同，则为同一个对象。
所以要在Student类里面重写equals()方法和hashCode()方法。
Integer类和String类本身都重写了equals()方法。
Student.java
package wgzyx;
public class Student {
private Long id;
private String name;
public Student() {
super();
}
public Student(Long id, String name) {
super();
this.id = id;
this.name = name;
}
public Long getId() {
return id;
}
public void setId(Long id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Student [id=" + id + ", name=" + name + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
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 (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
HashMapDemo.java
package wgzyx;
import java.util.HashMap;
import java.util.Set;
public class HashMapDemo {
public static void main(String[] args) {
HashMap<Student,String> mymap= new HashMap<Student,String>();
mymap.put(new Student(20L,"小红"),"考研");
mymap.put(new Student(20L,"小橙"), "保研");
mymap.put(new Student(21L,"小橙"), "考研");
mymap.put(new Student(20L,"小紫"), "保研");
mymap.put(new Student(20L,"小红"), "保研");
Set<Student> keys= mymap.keySet();
for(Student key: keys){
String value= mymap.get(key);
System.out.println(key.toString()+"---"+value);
}
}
}
网友评论