欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java中HashMap相关知识点

程序员文章站 2022-06-04 19:25:54
...

HashMap使用

哈希表
哈希表也称散列表,根据关键码值key 进行访问的数据结构,也就是说,能够将关键码映射到表中一个位置我们就可以去访问其记录value,加快查找的速度,这个映射函数叫做散列函数,存放记录的数组叫做散列表。
数组:寻址容易O(1),插入和删除困难O(N)
链表:寻址困难O(N),插入和删除容易O(1)
综合两者的特性,变成了一个寻址容易,插入删除也容易的数据结构哈希表有多种不同的结构(实现),我们介绍的是最常用的结构-拉链法(链地址法)
Map接口
Map,图,是一种存储键值对映射的容器,在Map中键可以是任意类型的对象,但是键不允许重复的,每一个键对应有一个值。

public class Hash {
    public static void main(String[] args) {
        //声明hashmap对象
        HashMap<String, Integer> map = new HashMap<>();

        //添加数据put
        map.put("a",1);
        map.put("b",2);
        map.put("c",3);
        map.put("d",4);
        map.put("e",5);

        //根据键获取值 key
        System.out.println(map.get("c"));

        //获取map中键值对的个数
        System.out.println(map.size());

        //判断map集合是否包含为key的键值对
        System.out.println(map.containsKey("d"));

        //判断map集合是否包含值为value的键值对
        System.out.println(map.containsValue(3));

        //根据键删除map中的键值对
        System.out.println(map.remove("e"));

        //获取hashmap中的所有键值对
        Iterator<Map.Entry<String,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<String, Integer> next = iterator.next();
            System.out.println(next.getKey()+":: "+next.getValue());
        }
    }
}

HashMap底层结构

HashMap基于哈希表的Map接口的非同步实现,继承自AbstractMap,AbstractMap是部分实现Map接口的抽象类。
jdk1.8之前:数组+链表
jdk1.8:数组+链表+红黑树
红黑树:
红黑树是一种自平衡二叉查找树 它在O(log2 N)的时间内做查找、添加、删除红黑树和AVL树是二叉查找树的变体,红黑树的性能要好于AVL树
红黑树特点:
1)每个节点是红色或黑色
2)根节点一定是黑色
3)每个叶子节点是黑色
4)如果一个节点是红色,则叶子节点必须是黑色
5)每个节点到叶子节点所经过的黑节点的个数必须是一样的。

当JVM存储HashMap的K-V时,仅仅通过Key来决定每一个Entry的存储槽位(Node[]中的index)。并且Value以链表的形式挂载到对应槽位上即可(1.8之后如果长度大于8则转为红黑树)。
HashMap之所以称之为HashMap是因为HashMap在put(String,Object)的时候JVM会对存入的对象进行一次hash(所有对象都是继承Object,而hashcode方法来自Object类中),从而获取到这个对象的hash值,接着JVM就根据这个hash值来决定该元素的存储位置。
如果发生两个Key存储到了同一个位置,则发生了Hash冲突(碰撞),Java采用的数组 + 链表方式就发挥作用了。Java采用链地址法(哈希值相同的元素构成一个链表,链表头指针指向Node[]的index),避免了Hash冲突的问题。Hash冲突发生后,这个槽位中存储的不是一个Entry而是多个Entry,此时就使用到了Entry链表。JVM是按照顺序去遍历每一个Entry,一直到查找到对应的Entry为止(链表查询)。如果hashcode相同,发生了hash冲突,新存入的值会覆盖旧的值,并且将旧的值返回。
HashMap扩容机制
HashMap中有resize(),当HashMap的元素个数超过数组的容量(length),进行扩容,默认情况下数组容量是16,当HashMap中的元素个数超过12个时,超过了临界值(就是源码中的threshold),需要把数组大小扩容一倍,然后通过rehash(重哈希),重新计算每个元素在数组中的位置。

HashMap源码分析

1)类的继承关系

public class HashMap<K,V> extends AbstractMap<K,V>
     implements Map<K,V>, Cloneable, Serializable

1、HashMap允许空值和空键
2、HashMap是非线程安全
3、HashMap元素是无序 LinkedHashMap TreeMap(HashTable不允许为空 线程安全)
2)类的属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16 默认初始容量 用来给table初始化
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f; //扩容机制
static final int TREEIFY_THRESHOLD = 8; //链表转为红黑树的节点个数
static final int UNTREEIFY_THRESHOLD = 6;//红黑树转为链表的节点个数
static final int MIN_TREEIFY_CAPACITY = 64;
static class Node<K,V> implements Map.Entry<K,V>
transient Node<K,V>[] table; //哈希表中的桶
transient Set<Map.Entry<K,V>> entrySet; //迭代器遍历的时候
transient int size;
int threshold;
final float loadFactor;

3)类中重要的方法(构造函数 put remove resize)
构造函数中并未给桶进行初始化
put方法

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
//resize()   初始化(和扩容)
if ((p = tab[i = (n - 1) & hash]) == null)
             tab[i] = newNode(hash, key, value, null);
//当前位置不存在节点,创建一个新节点直接放到该位置
else{
     //当前位置存在节点 判断key是否重复
     if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
         e = p;
        //判断第一个节点的key是否与所要插入的key相等
        //hashCode 表示将对象的地址转为一个32位的整型返回  不同对象的hashCode有可能相等
        //比较hash相比于使用equals更加高效
    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;
                      //判断e是否是key重复的节点
                 p = e;
            }
        }
 }

Hash算法
resize时机
1)table==null
2)table需要扩容的时候
过程
1)table进行扩容
2)table原先节点进行重哈希
a.HashMap的扩容指的是数组的扩容,因为数组的空间是连续的,所以需要数组的扩容即开辟一个更大空间的数组,将老数组上的元素全部转移到新数组上来
b.在HashMap中扩容,先新建一个2倍原数组大小的新数组,然后遍历原数组的每一个位置,如果这个位置存在节点,则将该位置的链表转移到新数组
c.在jdk1.8中,因为涉及到红黑树,jdk1.8实际上还会用到一个双向链表去维护一个红黑树中的元素,所以jdk1.8在转移某个位置的元素时,首先会判断该节点是否是一个红黑树解节点,然后遍历该红黑树所对应的双向链表,将链表中的节点放到新数组的位置当中
d.最后元素转移完之后,会将新数组的对象赋值给HashMap中table属性,老数组将会被回收。

HashMap常见面试题

1)JDK1.7与JDK1.8HashMap有什么区别和联系
2)用过HashMap没?说说HashMap的结构(底层数据结构 + put方法描述)
3)说说HashMap的扩容过程
4)HashMap中可以使用自定义类型作为其key和value吗?
5)HashMap中table.length为什么需要是2的幂次方
6)HashMap与HashTable的区别和联系
7)HashMap、LinkedHashMap、TreeMap之间的区别和联系?
8)HashMap与WeakHashMap的区别和联系
9)WeakHashMap中涉及到的强弱软虚四种引用
10)HashMap是线程安全的吗?引入HashTable和ConcurrentHashMap

相关标签: java hashmap