数据结构笔记
2-3树&红黑树
哈希表
哈希函数的设计
例如26个字符 new一个int[26]。可以用来做哈希
整型值
小范围正整数，直接使用正整数。
大整数 通常做法 取模 比如取后四位 mod 1000 模一个素数分布效果更好
如果对日期这种取模，只能在01-31，会造成分布不均匀。
要具体分析。
浮点型
32位或64位机器，浮点型会有特殊表示。
32位前8位
64位是前11位
使用整数的方式来解析
Java的hashCode
haseSet存数据，会先计算hashCode，有冲突则通过equals判断是否是同一个对象。
哈希冲突
链地址法
- 数组，长度M
- 元素对M取模
- (hashCode(k1) & 0x7fffffff) % M
- 前面是31位的0做与，去掉第一位的符号位。
- 算完模后，例如4，索引为4的位置，就存上就好了。
- 有冲突时
- 在链表尾部加冲突的节点。
- 也可以用平衡树存
扩容 hashMap 默认 数组长度*0.75 即 16*0.75=12 12个长度就扩容。
开放地址法
所有索引都有机会存不同的hash值。
正常先存储，遇到hash冲突，就把冲突的元素，向后去找空的空间。
比如对10取hash值。
占满了，就会一直探测。
改进：
平方探测法
每次向下找平方，不是+1
二次hash法
对于开放地址法，扩容合适，也是O(1)复杂度
再Hash法 Rehashing
Coalesced Hashing
结合seperate Chaining 和 Open Addressing
SQRT O(sqrt(n)) 根号N时间复杂度
代码实现更方便，虽然时间复杂度会比线段树O(logn)高一些。
分块分组的思想，解决区间问题。
todo