哈希（哈希散列数据结构）---底层原理

Day02:

1.哈希散列数据结构：底层实现就是：数组+链表（红黑树）

map的put方法和get方法。

2.数组方法和链表存取数据的区别

数组方法：法随机访问快

链表：增删改效率快。

3.哈希结合了链表和数组的特性。

哈希算法的规则：哈希值是c++写的。

面试常问：

java中哈希算法：

保证了数组长度必定是0-2n

元素的个数永远小于数组的长度。扩充因子，就导致元素个数永远小于元素长度。

扩容会引起哈希map中的值变化，其每哈希一边就会更新一边元素存放的位置，哈希表的

哈希散列表：解决了即需要随机访问，又要增删改快的问题

哈希散列算法的原理：

（1）链地址法（java中使用）邻接表法（处理冲突的方式是以当前位置创建一个链表出来）直接定址法（浪费空间）。

（2）开放寻址法（处理哈希冲突）

哈希函数：1。取余法 H(Key)=key%p;p是指最大容量。

Ridas满足一致性哈希原则：解决了雪崩。

服务器不满足一致性哈希原则：

      

一致性哈希：会出现雪崩

稀疏数组（稀疏矩阵就是一个二维数组）：应用场景(棋盘)

行列值和状态都是有用的。

棋盘代码（js简单代码）：