HashMap:
jdk1.7和1.8的区别：
jdk7的HashMap使用的数据结构是：数组+链表
jdk8中会将链表转成红黑树（链表的长度超过8的时候），数组+链表+红黑树
为什么转成红黑树？链表的插入效率很高，但是查询效率较低，完全平衡二叉树的查询效率很高，但是插入效率很低，于是在链表和完全平衡二叉树之间做了一个折中，采用的是红黑树。
但是remove操作之后，如果红黑树的节点个数小于6，那么又会转成链表。
jdk1.8之后为什么会在链表和红黑树之间进行转换呢？主要是提高HashMap的查询和插入的性能
查询效率：完全平衡二叉树>红黑树>链表
插入效率：链表>红黑树>完全平衡二叉树
新节点插入链表的位置不同（1.7是头插，1.8是尾插）
1.8的hash算法简化
resize的逻辑修改（jdk7会出现死锁，jdk8不会,jdk7链表元素位置会逆序）
HashMap的几个重要参数：
// HashMap默认的数组初始值大小.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//在构造函数中未指定时使用的负载系数.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//如果添加元素时链表的节点个数大于8，将链表转成红黑树
static final int TREEIFY_THRESHOLD = 8;
//如果删除元素时红黑树的节点个数小于6，将红黑树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树最小长度为 64
static final int MIN_TREEIFY_CAPACITY = 64;
jdk7与jdk8的hashmap的数据结构示意图：
代码示例：
public class HashMapTest {
public static void main(String[] args) {
Map<String,String> map=new HashMap<>();
map.put("周瑜","周瑜");
map.put("刘备","刘备");
map.put("孙权","孙权");
map.put("曹操","曹操");
map.put("张飞","张飞");
for (String key:map.keySet()) {
int code=key.hashCode(); //生成每个key的hashcode
假设此时有一个容量为8的hashMap
int index=code%8; //将每一个hashcode余8
System.out.println(String.format("%s的hashcode是%s，index=%s",key,code,index));
}
}
}
运行结果：
孙权的hashcode是751370，index=2
张飞的hashcode是794046，index=6
刘备的hashcode是674287，index=7
曹操的hashcode是842996，index=4
周瑜的hashcode是699636，index=4
上述代码的hashmap的示例图：
jdk1.7
jdk1.8
HashMap的扩容的时机：
当HashMap中的元素个数达到：加载因子 * HashMap的容量 时，HashMap会扩容为：HashMap容量*2。
hashmap的扩容示意图：
jdk1.7
jdk1.8
上述示意图可以看出jdk1.7的hashamp扩容会导致链表部分的元素的顺序发生逆序，1.8则不会。
HashMap为什么是线程不安全的：
在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
加载因子为什么是0.75：
hashmap的源码：
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*
使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素个数和概率的对照表。
从上面的表中可以看到当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。
加载因子是表示Hash表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。
冲突的机会越大,则查找的成本越高。反之,查找的成本越小。
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷。
HashMap为什么要重写hashCode 和equals方法：
HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据 equals 方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry 时，也会根据 hash 算法找到其在数组中的存储位置，再根据 equals 方法从该位置上的链表中取出该Entry。
equals如果一般不重写的话，它是通过==来比较两个对象的引用地址
public boolean equals(Object obj) {
return (this == obj);
}
手写简单的HashMap：
public class MyHashMap<K,V> {
//数组
private Entry[] table;
//hashMap的大小
private int size;
//数组的初始化大小
private static Integer CAPACITY =8;
//构造方法初始化数组
public MyHashMap() {
this.table = new Entry[CAPACITY];
}
//获取hashmap的元素的个数
public int size(){
return size;
}
//获取hashmap的元素
public Object get(K k){
int code=k.hashCode(); //生成每个key的hashcode
int i=code%8; //将每一个hashcode余8 获取数组的下标
for(Entry<K,V> entry=table[i];entry!=null;entry=entry.next){
if(entry.k.equals(k)){
return entry.v;
}
}
return null;
}
//添加值到hashmap
public Object put(K k,V v){
int code=k.hashCode(); //生成每个key的hashcode
int i=code%8; //将每一个hashcode余8 获取数组的下标
//put相同的key，但是value不同，新的value替换旧的value 并返回新的值
//遍历链表
for(Entry<K,V> entry=table[i];entry!=null;entry=entry.next){
if(entry.k.equals(k)){
V old=entry.v;
entry.v=v;
return old;
}
}
addEntry(k,v,i);
return null;
}
//添加节点
public void addEntry(K k,V v,int i){
//增加节点
Entry entry=new Entry<> (k, v, table[i]);
//头节点下移
table[i]=entry;
size++;
}
//定义Entry（链表节点）
class Entry<K,V> {
private K k;
private V v;
private Entry<K,V> next;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
}
//测试
public static void main(String[] args) {
MyHashMap<String,String> hashMap=new MyHashMap<>();
hashMap.put("key","value");
System.out.println(hashMap.get("key"));
System.out.println( hashMap.put("key","value1"));
System.out.println(hashMap.get("key"));
System.out.println(hashMap.size);
}
}
京公网安备 11010502036488号