HashMap几个关键的属性–
存储数据的数组
transient Node<K,V>[] table;
默认容量 ----
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
最大容量 static final int MAXIMUM_CAPACITY = 1 << 30;
加载因子是一个比例，当HashMap的数据大小>=容量加载因子时，HashMap会将容量扩容
默认加载因子----
static final float DEFAULT_LOAD_FACTOR = 0.75f;
当实际数据大小超过threshold–阈值时(如当实际数据大小超过160.75=12时会扩容,重新计算存储位置)，HashMap会将容量扩容，
threshold＝容量*加载因子 int threshold;
加载因子 —
final float loadFactor;
import java.util.HashSet;
import java.util.Set;
/**
* @author : Gavin
* @date: 2021/7/18 - 07 - 18 - 9:13
* @Description: setTest
* @version: 1.0
*/
class Person{
String name;
int age;
String gender;
public Person(String name, int age, String gender) {
this.name = name;
this.age = age;
this.gender = gender;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
", gender='" + gender + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person person = (Person) o;
if (age != person.age) return false;
if (!name.equals(person.name)) return false;
return gender.equals(person.gender);
}
@Override
public int hashCode() {
int result = name.hashCode();
result = 31 * result + age;
result = 31 * result + gender.hashCode();
return result;
}
}
public class setHash {
public static void main(String[] args) {
Set<Person> hashSet= new HashSet<>();
Person per= new Person("李一狗",18,"男");
Person per1= new Person("李二狗",19,"男");
Person per2= new Person("李三狗",20,"男");
Person per3= new Person("李四狗",21,"男");
Person per4= new Person("李一狗",18,"男");
Person per5= new Person("李六狗",23,"男");
hashSet.add(per);
hashSet.add(per1);
hashSet.add(per2);
hashSet.add(per3);
hashSet.add(per4);
hashSet.add(per5);
// 遍历
for (Person s:hashSet
) {
System.out.println(s);
}
}
}
HasSet无序,且不允许添加重复元素
接下来分析一下HashSet的底层是怎么实现的,使用的最新版本jdk16(我有个习惯喜欢追求最新的)
创建对象---
```java
Set<Person> hashSet= new HashSet<>();
```
构造方法---
```java
public HashSet() { map = new HashMap<>(); }
```
发现HashSet构造中创建了一个HashMap对象
```java
public HashMap() {//无参数的构造函数，加载因子为默认加载因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
```
> 在HashMap中有几个重要参数-- static final float DEFAULT_LOAD_FACTOR = 0.75f;
> final float loadFactor;
再来看add()方法---add(per)
```java
public boolean add(E e) {//添加Person对象per
return map.put(e, PRESENT)==null;
}
```
这里继续看map,present与put分别代表什么----
```java
//present为Object对象
private static final Object PRESENT = new Object();
```
```java
private transient HashMap<E,Object> map;
```
这里是创建的HashMap对象map,调用put方法
```java
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
```
> return map.put(per, PRESENT)==null; 这里put(per, PRESENT)返回的一个present对应类型的数据--这里是Object类型的,如果返回值为null,则add返回true说明添加成功,否则返回false.添加失败;
再来看---put方法中调用的putVal方法(看起来比较复杂)
传入的参数---
int类型的hash(per)--哈希值,
Person类型的per,
Object类型的 Present
boolean类型的 false
boolean类型的true
> HashMap中的重要属性 ----
> transient Node<K,V>[] table;
> final int hash;
> final K key;
> V value;
>
再看putVal方法之前先看一下resize()方法
```java
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//将oldTab指向table
//如果oldTab == null,那么为第一次添加oldCap=0,(如果不是第一次,那么oldCap=oldTab的长度)
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//----- int oldCap=0
// field holds the initial array capacity, or zero signifying
int oldThr = threshold;//threshold初始值为0--初始化集合
int newCap, newThr = 0;
if (oldCap > 0) {//-----若 int oldCap>0,说明不是第一次添加,oldCap=oldTab的长度
if (oldCap >= MAXIMUM_CAPACITY) {
// static final int MAXIMUM_CAPACITY = 1 << 30;--一个很大的数了2^31--(计算的时候位移的效率更高)
threshold = Integer.MAX_VALUE;//也是一个很大的数了
return oldTab;//返回oldTab
}
/**0<oldCap < MAXIMUM_CAPACITY左移一位相当于newCap的平方
newCap^<2^31并且oldCap>=DEFAULT_INITIAL_CAPACITY(初始值为2^4=16)--*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//将旧的长度的平方赋值给新长度,
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//默认16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16
}
if (newThr == 0) {//如果长度为0,开辟新长度
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
```
resize主要是用来扩充大小用的,返回 一个新的newTab
```java
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;//创建新对象tab
Node<K,V> p; //创建新对象p
int n, i;//int 类型的 n,i
if ((tab = table) == null || (n = tab.length) == 0)//如果tab为空或者tab的长度为0,那么重新为n赋值,
n = (tab = resize()).length;//
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//这里决定了不能添加重复元素
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
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;
}
```
做好笔记啊......
为什么是
“e.hash& (newCap-1)”这样做是为了提高HashMap的效率。
首先我们要确定一下，HashMap的默认长度为16,扩容的时候是乘以2^n,因此数组长度一定是偶数，在实际容量达到 容量*0.75即12时开始扩容，
```java
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
```
小总结----
所以length-1位奇数，奇数\偶数有什么不同呢?
提高存储位置的均匀性,避免某位置存储过多,而其它位置过少的问题;
hashMap在每次插入数据前，会检查table数组的实际容量，如果实际容量>=初始容量，则把table的初始容量扩为原来的2倍，这时，就需要一个一个复制原来的数据项了，这是比较费时的！所以，初始容量很重要。
由于扩容后要重新计算存储位置,数据量小还可以,如果时千万级的数据,内存的开销---cpu的开销非常大,所以一开始最好是预估一下存储的数量;
在高并发情况下最好不使用HashMap,HashMap是线程不安全的，如果被多个线程共享的操作--后果可想而知------
