浅谈HashMap

导言:

数组在O(1)时间复杂度可以定位元素(读),但是随机插入元素(写)效率比较低。而链表则相反,随机插入元素效率很高,但是随机读取效率低。

那有没有,读取和插入效率都很高的数据结构呢?

答案当然是有,HashMap就是一种读取和插入效率都很高的数据结构。

基础特性

HashMap的几个必要的基础特性:

  • hashCode()
  • KV键值对
  • 数组为基础,辅助以链表的数据结构

因为是散列函数,实际的键在数组中是分散存在的,占有一定的比例,如果比例高的时候容易出现键一样值不一样的情况(在该处形成链表),所以有初始容量和加载因子两个参数。

通常,默认加载因子是0.75,这是在时间和空间上的一种折中。

存储节点

HashMap中的Key-Value都是存储在Entry数组中的。

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    // 指向下一个节点
    Entry<K,V> next;
    final int hash;

    //...other
}

常用用法

clear()--清空HashMap
boolean containsKey(Object key)
boolean containsValue(Object value)
getEntry(Object key)

entrySet()/values()/keySet()

get(Object key)
put(Object key,Object value)

新的理解和问题

HashMap是一个数组,每个元素都是一个链表。由链表组成的数组。
HashMap属于Key-Value型数据结构。Key与元素在数组中的位置有关,插入顺序与元素在链表中的位置有关。引出问题:从Key到数组序号是怎么映射的,有哪些问题(怎样减少重复而且均匀、重复之后怎么办)被引入,又是怎么解决的。关键词:均匀不重复、Key+key.hashCode()查找元素。
HashMap的基础是数组,怎样扩容,扩容是的元素重排是怎样的。