7.跳錶:各方面都非常優秀的動態數據結構
跳錶基於單鏈表實現,鏈表查找、插入、刪除絕大部分時間花在遍歷鏈表上,跳錶使用索引來優化鏈表遍歷的過程,使得跳錶具有非常優秀的查找、插入、刪除性能,並且是天然的動態數據結構
-
查找、插入、刪除時間複雜度都是O(logn)
-
跳錶原理的理解
-
二叉搜索通過計算mid的值,使得每一次要遍歷的數據量減半,那麼鏈表可不可以實現類似的功能呢
-
如果有一個指針指向鏈表中點,那麼在搜索時先與中點比較,根據比較結果決定是從鏈表頭開始遍歷還是從中點開始遍歷,這樣平均每次要遍歷的數據量就減少了一半
-
如果多設置幾個索引,甚至設置多級索引,那麼遍歷鏈表所花費的時間將大大降低,而額外付出的空間不過是幾個指針
-
跳錶示意圖
-
原鏈表查找4,需要1->2->3->4,而加了索引之後1->3->4;查找5更是只需1->5;在鏈表很大時跳錶的查找效率會顯著提高。
-
-
跳錶實現上的注意點
-
與紅黑樹相比跳錶的實現難度要簡單不少,但還是有幾處注意點
-
節點設置
-
數據(data):存儲該節點數據
-
索引數組(forward[]):存儲該節點各層的索引(每個索引也是一個節點),索引指是指向下一節點的指針
-
查找結點(值設為value)
-
-
實際上跳錶實現的核心就是結點的查找
- 查找時從頭節點、最上層索引開始
-
找到該層索引中data小於value的最大節點(這個節點後面的節點值要麼等於value要麼大於value)
-
若本層已經是第0層索引(也就是到了原鏈表)則此時的節點就是值小於等於value的最後一個節點,這個節點後面一個就是我們要找的值
-
若本層不是第0層索引,則去下一層,重複1-2-3過程
-
跳錶Java實現(insert優化)
/**
* 跳錶是在單鏈表的基礎上加入索引,使查找效率大大提高的一種各方面性能都很優秀的數據結構
*
* @author hzk
*/
public class mySkipList {
private final int MAX_LEVEL = 16;//最大索引層數(0~原鏈表 15~最高一級索引)
private int levelCount = 1;//跳錶當前索引層數
public Node head = new Node();//跳錶頭
/**
* 查找跳錶中值為value的節點
*
* @param value 要查找的值
* @return 找到返回對應節點,否則返回null
*/
public Node find(int value) {
Node p = head;
//找到該層索引中小於value的最大節點
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value)
return p.forwards[0];
else
return null;
}
/**
* 將value插入跳錶中
*
* @param value 待加入數據
*/
public void insert(int value) {
int level = randomLevel();
if (levelCount < level) levelCount = level;
Node p = head;
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node path[] = new Node[level];//存儲查找value時經過各層的索引
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
path[i] = p;
}
//將value插入各層索引中
for (int i = level - 1; i >= 0; i--) {
newNode.forwards[i] = path[i].forwards[i];
path[i].forwards[i] = newNode;
}
}
/**
* insert的優化版本,去掉了path[]
* @param value 待加入數據
*/
public void insert_optimized(int value) {
int level = randomLevel();
if (levelCount < level) levelCount = level;
Node p = head;
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value)
p = p.forwards[i];
//這層索引是最後一個則直接插入
if (p.forwards[i] == null) {
p.forwards[i] = newNode;
}
//否則插在中間
else {
newNode.forwards[i] = p.forwards[i];
p.forwards[i] = newNode;
}
}
}
/**
* 刪除跳錶中值為value的節點及索引
*
* @param value 待刪除結點的值
*/
public void delete(int value) {
Node path[] = 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];
path[i] = p;
}
//找到
if (p.forwards[0] != null && p.forwards[0].data == value) {
//刪除節點所有索引
for (int i = levelCount - 1; i >= 0; i--) {
if (p.forwards[i] != null && p.forwards[i].data == value) {
p.forwards[i] = p.forwards[i].forwards[i];
}
}
}
}
/**
* 隨機生成索引層數,索引層數和生成概率負相關
* 盡量使一級索引佔全部索引的50%,二級索引佔25%,三級索引佔12.5%……
* 隨機函數能放置數據全部集中在某兩個索引之間
*
* @return
*/
private int randomLevel() {
int level = 1;
while (Math.random() < 0.5 && level < MAX_LEVEL)
level++;
return level;
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0].data + " ");
p = p.forwards[0];
}
System.out.println();
}
public void skipListText() {
mySkipList list = new mySkipList();
list.insert(1);
list.insert(2);
list.insert(3);
list.printAll();
System.out.println(list.find(2));
list.delete(2);
list.printAll();
list.insert_optimized(2);
list.printAll();
}
public class Node {
private int data = -1;//節點數據
private Node forwards[] = new Node[MAX_LEVEL];//存儲節點上層索引
private int maxLevel = 0;//最大索引層數
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
}