导言:
数组在O(1)时间复杂度可以定位元素(读),但是随机插入元素(写)效率比较低。而链表则相反,随机插入元素效率很高,但是随机读取效率低。
那有没有,读取和插入效率都很高的数据结构呢?
答案当然是有,HashMap就是一种读取和插入效率都很高的数据结构。
基础特性
HashMap的几个必要的基础特性:
- hashCode()
- KV键值对
- 数组为基础,辅助以链表的数据结构
因为是散列函数,实际的键在数组中是分散存在的,占有一定的比例,如果比例高的时候容易出现键一样值不一样的情况(在该处形成链表),所以有初始容量和加载因子两个参数。
通常,默认加载因子是0.75,这是在时间和空间上的一种折中。