数据结构--跳表，散列表
跳表
跳表是一种动态的数据结构，给原始的链表增加多级的索引，因此跳表的查询的时间复杂度为O(m * logn)，m取决于跳表的跳跃的距离,空间复杂度为O(N),跳表是通过随机函数来维持跳表的平衡性，避免导致退化为线性表
package com.xx;
import java.util.Random;
/**
* 跳表
*/
public class MySkipList {
/**
* 最大的深度
*/
private static final int MAX_LEVEL = 16;
/**
* 实际层数
*/
private int levelCount = 1;
/**
* 带头的链表
*/
private Node head = new Node(MAX_LEVEL);
private Random r = new Random();
/**
* 查找
* @param value
* @return
*/
public Node find(int value){
Node curr = head;
// 从上往下找
for (int h = levelCount - 1; h >= 0 ; h --){
while (curr.forwards[h] != null && curr.forwards[h].data < value ){
curr = curr.forwards[h];
}
}
if (curr.forwards[0] != null && curr.forwards[0].data == value){
return curr.forwards[0];
}else{
return null;
}
}
/**
* 插入
* @param value
*/
public void insert(int value){
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层，如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node[] update = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level，所以加上判断
if (level > i) {
update[i] = p;
}
}
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}
/**
* 对应level添加数据
* @param value
* @param level
*/
public void insert(int value , int level){
// 随机一个层数
if (level == 0) {
level = randomLevel();
}
// 创建新节点
Node newNode = new Node(level);
newNode.data = value;
// 表示从最大层到低层，都要有节点数据
newNode.maxLvl = level;
// 记录要更新的层数，表示新节点要更新到哪几层
Node[] update = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
/**
*
* 1，说明：层是从下到上的，这里最下层编号是0，最上层编号是15
* 2，这里没有从已有数据最大层（编号最大）开始找，（而是随机层的最大层）导致有些问题。
* 如果数据量为1亿，随机level=1 ，那么插入时间复杂度为O（n）
*/
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// 这里update[i]表示当前层节点的前一节点，因为要找到前一节点，才好插入数据
update[i] = p;
}
// 将每一层节点和后面节点关联
for (int i = 0; i < level; ++i) {
// 记录当前层节点后面节点指针
newNode.forwards[i] = update[i].forwards[i];
// 前一个节点的指针，指向当前节点
update[i].forwards[i] = newNode;
}
// 更新层高
if (levelCount < level) levelCount = level;
}
public void delete(int value){
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
/**
* 打印每个节点数据和最大层数
*/
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
/**
* 打印所有数据
*/
public void printAllBeautiful() {
Node p = head;
Node[] c = p.forwards;
Node[] d = c;
int maxLevel = c.length;
for (int i = maxLevel - 1; i >= 0; i--) {
do {
System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
} while (d[i] != null && (d = d[i].forwards)[i] != null);
System.out.println();
d = c;
}
}
/**
* 随机level
* @return int
*/
private int randomLevel(){
int level = 1;
for (int i = 1; i < MAX_LEVEL ; i++) {
if (r.nextInt() % 2 == 1){
level ++;
}
}
return level;
}
}
class Node{
/**
* 对应的数据
*/
int data = -1;
/**
* 表示当前节点位置的下一个节点所有层的数据
*/
Node[] forwards;
int maxLvl = 0;
public Node(int level) {
forwards = new Node[level];
}
@Override
public String toString() {
return "{ data: " +
data +
"; levels: " +
maxLvl +
" }";
}
}
散列表
一种k-v形式的数据结构，具有高效的查询时间复杂度 O(1),但哈希函数可能导致哈希冲突；
解决哈希冲突的方法有开放寻址法，链表法；
- 开放寻址法:出现冲突时，重新探测一个空闲的位置，插入；
线性探测法:线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久. - 链表法: 链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。我们来看这个图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
散列表与链表结合
LRU缓存淘汰算法
LinkedHashMap： 按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统；LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。
哈希算法应用
- 安全加密 最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。
- 唯一标识 我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
- 数据校验 我们通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。
- 散列函数
区块链使用的哈希算法
区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。
区块头保存着 自己区块体 和 上一个区块头 的哈希值。
因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。
区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。
哈希算法在分布式中的使用
- 负载均衡 负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？ 我们可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号
- 数据分片 统计一个关键词出现的次数 我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。
- 分布式存储