hashMap索引原理

平日里面经常使用map这种数据结构，令人称奇的是他的访问速度为什么那么快？为什么可以通过key以接近O(1)的速度查找？

一、基础数据结构特点分析

1.1数组

查找的时间复杂度为O(1)

插入时间复杂度为O(n)

1.2链表

查找的时间复杂度为O(n)

插入时间复杂度为O(1)

1.3红黑树

一种平衡树，能以较低的时间复杂度进行搜索、添加和查找操作O（logn）

可以优化节点查找速度

所以如果我们能找到一种，通过数组进行范围筛选，通过链表对数据进行增删的数据结构来存储数据，那么就能够获得较快的查询速率

二、hashMap基本实现原理

2.1hash过程

将这个数据节点进行hasCode操作，获取一个hash值

2.2hash定位

hash值对数组长度取模，获取一个模值，相同模值的数据节点挂载在同一个链表上

2.3查找

获取数据的时候就将该key转成hash，计算其模值，在对应的链表上面进行顺序查找

2.4hash冲突过多的优化

什么是hash冲突？：不同的key算出了相同的hash

解决方案1（Java采用）——链地址法：相同的hash值转到一个链表，链表长度大于8转换成红黑树，红黑树规模小于6退化成链表

特点：

（1）要减少hash冲突需要很大的散列，利用率不够大

（2）默认大小为16，超过就扩充一倍

解决方案2（Python采用）——开放寻址法：算出了相同的hash值就继续往下遍历寻找第一个找到的空hash值

特点：

（1）适用于负载不大的散列，负载过大会长时间找不到空hash

（2）负载超过一定阙值就扩容，而不是满了再扩容