数组
基础概念
连续的，支持根据index快速检索数据（随机访问），但是对于任意位置添加或任意位置删除时间复杂度存在最好和最坏的情况。
栈
栈是一种线性结构，相比数组，栈对应的操作是数组的子集，只能从一端添加元素，也只能从一端取出元素，此端为栈顶。
后进先出的数据结构，Last In First Out(LIFO)
程序调用的系统栈，A方法调用B方法调用C方法，AB都在系统栈中，当C方法调用完后，下次调用的是B方法。
可以利用数组和队列来实现，利用数组实现可以向数组尾部插入数据，并且从尾部读取数据。
队列
队列是一种线性结构，底层可以用动态数组实现，是一种FIFO(先进先出)的数据结构。
循环队列
利用index来记录队头和队位标示来记录队列的情况。
public class LoopQueue<E> implements Queue<E> {
private E[] data;
// 队首索引
private int front;
// 队尾索引
private int tail;
private int size;
public LoopQueue(int cap) {
/**
* 会浪费一个位置，front==tail为null front==tail+1 队列满
*/
this.data = (E[]) new Object[cap + 1];
}
public LoopQueue() {
this(10);
}
public int getCap() {
return data.length - 1;
}
private boolean isValid() {
// 防止数据越界
return (this.tail + 1) % data.length == front;
}
private void resize(int cap) {
E[] resizeQueue = (E[]) new Object[cap + 1];
for (int i = 0; i < size; i++) {
// 防止数组越界
resizeQueue[i] = data[(i + front) % data.length];
}
data = resizeQueue;
front = 0;
tail = size;
}
@Override
public void enqueue(E e) {
// 扩容
if (isValid()) {
resize(getCap() * 2);
}
this.data[this.tail] = e;
tail = (tail + 1) % data.length;
size++;
}
@Override
public E dequeue() {
if (isEmpty()) {
throw new NullPointerException("循环队列为空");
}
E ret = data[front];
// help gc
data[front] = null;
front = (front + 1) % data.length;
size--;
// lazy 缩容
if (this.size == getCap() / 4 && getCap() / 2 != 0) {
resize(getCap() / 2);
}
return ret;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new NullPointerException("循环队列为空");
}
return data[front];
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return this.front == this.tail;
}
@Override
public String toString() {
return "LoopQueue{" +
"data=" + Arrays.toString(data) +
", front=" + front +
", tail=" + tail +
", size=" + size +
'}';
}
public static void main(String[] args) {
LoopQueue<Integer> loopQueue = new LoopQueue<>();
for (int i = 0; i < 4; i++) {
loopQueue.enqueue(i);
}
System.out.println(loopQueue.getCap());
System.out.println(loopQueue.dequeue());
System.out.println(loopQueue.getFront());
System.out.println(loopQueue);
}
}
链表
线性结构，动态的数据结构不需要处理固定容量的问题，更深入的理解引入(或者指针)。
深入理解的递归结构，数据存储在"节点(Node)"中
public class LinkedList<E> {
private class Node {
E data;
Node next;
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
public Node(E data) {
this.data = data;
this.next = null;
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return data.toString();
}
}
private int size;
private Node dummyHead;
public LinkedList() {
this.size = 0;
this.dummyHead = new Node();
}
public int getSize() {
return this.size;
}
public boolean isEmpty() {
return this.size == 0;
}
public void add(int index, E e) {
indexValid(index);
Node pred = this.dummyHead;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = new Node(e, pred.next);
size++;
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public E get(int index) {
indexValid(index);
Node cur = dummyHead.next;
int i = 0;
while (cur != null) {
if (i == index) {
return cur.data;
}
cur = cur.next;
i++;
}
return null;
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size - 1);
}
public void set(int index, E e) {
indexValid(index);
Node cur = this.dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.data = e;
}
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (e == cur.data) {
return true;
}
cur = cur.next;
}
return false;
}
public void remove(int index) {
indexValid(index);
Node prev = this.dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node deleteNode = prev.next;
prev.next = deleteNode.next;
// 移除删除节点引用
deleteNode.next = null;
size--;
}
private void indexValid(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed.Illegal index.");
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
res.append(cur).append("->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
二分搜索树(非线性数据结构)
特点
二分搜索数时二叉树
二分搜索数的每个节点的值都大于其左子树所有节点的值，小于其右子树的所有节点的值。
遍历
前序遍历
//根 左 右
public void preOrder(Node<E> node) {
if (node != null) {
// 访问根节点
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
}
// 非递归方式
private void preOrderNR() {
Stack<Node<E>> stack = new Stack<>();
if (root != null) {
stack.push(root);
while (!stack.isEmpty()) {
Node<E> cur = stack.pop();
System.out.println(cur.e);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
}
中序遍历
// 左 根 右
public void inOrder(Node<E> node) {
if (node != null) {
inOrder(node.left);
// 访问根节点
System.out.println(node.e);
inOrder(node.right);
}
}
后序遍历
// 左 右 根
public void postOrder(Node<E> node) {
if (node != null) {
preOrder(node.left);
preOrder(node.right);
System.out.println(node.e);
}
}
层序遍历
根据树的深度去遍历(BFS，广度优先遍历)，利用队列一层一层进行遍历,能够更快的找到搜索的元素
public void bfs() {
Queue<Node<E>> queue = new LinkedList<>();
if (root != null) {
queue.add(root);
while (!queue.isEmpty()) {
Node<E> cur = queue.remove();
System.out.println(cur.e);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
}
删除节点
删除左右都有孩子的节点d
s->right=delMin(d->right)
/**
* 最小值的节点
*
* @return
*/
public Node<E> minimum(Node<E> node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
public E maximum() {
if (root == null) {
throw new IllegalArgumentException();
}
return maximum(root).e;
}
/**
* 最大值节点
*
* @param node
* @return
*/
public Node<E> maximum(Node<E> node) {
if (node.right == null) {
return node;
}
return maximum(node.right);
}
public E removeMin() {
E ret = minimum();
root = removeMin(root);
return ret;
}
private Node<E> removeMin(Node<E> node) {
if (node.left == null) {
Node<E> rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
public E removeMax() {
E maximum = maximum();
root = removeMax(root);
return maximum;
}
public Node<E> removeMax(Node<E> node) {
if (node.right == null) {
Node<E> leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
public void remove(E e) {
root = remove(root, e);
}
private Node<E> remove(Node<E> node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {
if (node.left == null) {
Node<E> rightNode = node.right;
node.right = null;
size--;
return rightNode;
} else if (node.right == null) {
Node<E> leftNode = node.left;
node.left = null;
size--;
return leftNode;
} // 如果存在左右孩子节点，找到node的后继，右节点的左节点
Node<E> successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
return successor;
}
}
/**
* 使用删除节点的前驱来替代删除的节点
*
* @param node
* @param e
* @return
*/
private Node<E> remove1(Node<E> node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {
if (node.left == null) {
Node<E> rightNode = node.right;
node.right = null;
size--;
return rightNode;
} else if (node.right == null) {
Node<E> leftNode = node.left;
node.left = null;
size--;
return leftNode;
} // 如果存在左右孩子节点，找到node的前驱，右节点的左节点
Node<E> successor = maximum(node.left);
successor.left = removeMax(node.left);
successor.right = node.right;
return successor;
}
}
堆和优先队列
优先队列
堆
父亲节点index是(childIndex-1)/2,LeftChildIndex=parentIndex * 2+1,RightChildIndex=parentIndex * 2+2
线段树
每个节点表示的都是一个区间内的数据,子节点都是区间的拆分，直到最终的子叶节点存储的为一个长度的区间。
字典树
public class Trie {
private static class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
public int size() {
return size;
}
public void add(String word) {
Node cur = this.root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!cur.next.containsKey(c)) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
}
size++;
}
public boolean contains(String word) {
Node cur = this.root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.containsKey(c)) {
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
public boolean isPrefix(String prefix) {
Node cur = this.root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.containsKey(c)){
return false;
}
cur = cur.next.get(c);
}
return true;
}
}
并查集
概念
实现
Quick Union Find
public class QuickUnionFind implements UnionFind {
// 每个数据对应的集合的编号
private int[] id;
public QuickUnionFind(int size) {
id = new int[size];
// 将集合编号指向自己
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
@Override
public int getSize() {
return id.length;
}
@Override
public boolean isConnected(int p, int q) {
// p和q所存储的集合编号是否相等
return find(p) == find(q);
}
/**
* O n
*
* @param p
* @param q
*/
@Override
public void unionElements(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
for (int i = 0; i < id.length; i++) {
if (id[i] == rootP) {
id[i] = rootQ;
}
}
}
/**
* 查找元素p对应的编号
*
* @param p
* @return
*/
private int find(int p) {
if (p < 0 || p >= id.length) {
throw new IllegalArgumentException();
}
return id[p];
}
}
Tree Uinon Find
public class TreeUnionFind implements UnionFind {
private int[] parent;
private int count;
private int[] size;
public TreeUnionFind(int count) {
this.count = count;
size = new int[count];
parent = new int[count];
// 节点指向自己
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
size[i] = 1;
}
}
@Override
public int getSize() {
return count;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 防止数据倾斜将小树接到大树下, size优化
if (size[rootP] >= size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException();
}
while (parent[p] != p) {
// 路径压缩，减少遍历数据深度
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
}
rank和路径压缩
public class TreeUnionFind1 implements UnionFind {
private int[] parent;
private int count;
private int[] rank;
public TreeUnionFind1(int count) {
this.count = count;
rank = new int[count];
parent = new int[count];
// 节点指向自己
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
return count;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 防止数据倾斜将小树接到大树下, size优化
if (rank[rootP] > rank[rootQ]) {
parent[rootQ] = rootP;
} else if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else {
parent[rootP] = rootQ;
rank[rootQ] += 1;
}
count--;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException();
}
while (parent[p] != p) {
// 路径压缩，减少遍历数据深度
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
}
AVL树
平衡二叉树
对于任意一个节点，左子树和右子树的高度差不能为超过1。
标注节点的高度，计算平衡因子，平衡因子为高度差，一旦其绝对值大于等于2则不为平衡二叉树。
左旋转和右旋转
右旋转
插入的元素在不平衡的节点的左侧的左侧，此时可以使用右旋转保证树的平衡
将原本的根节点y顺时针旋转到x的右子树，x为新的根节点。
# 右旋转调节
if( balanceFactor > 1 && getBalanceFactor(node.left) > 0){
return rightRotate(node);
}
private Node<E> rightRotate(Node<E> y) {
Node<E> x = y.left;
Node<E> T3 = x.right;
// 向右旋转
x.right = y;
y.left = T3;
// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
左旋转
# 左旋转条件
if (balanceFactor<-1&&getBalanceFactor(node.right)<=0){
return leftRotate(node);
}
/**
* y x
* / \ / \
* T1 x y z
* /\ ------->向左旋转 / \ / \
* T2 z T1 T2 T3 T4
* /\
* T3 T4
* @param y
* @return
*/
private Node<E> leftRotate(Node<E> y) {
Node<E> x = y.right;
Node<E> T2 = x.left;
// 向左旋转
x.left = y;
y.right = T2;
// 更新height
y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;
return x;
}
LR
# 满足LR的条件
// 左子树大于右子树，并且左子树的左子树小于左子树的右子树
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
RL
先对x节点进行右旋转,转换成了RR，再进行左旋转。
# 满足RL的条件
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
红黑树
特点
红黑树是保持"黑平衡"的二叉树，严格意义上不是平衡二叉树，最大高度是:2logn O(logn)
import java.util.ArrayList;
public class RBTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{
public K key;
public V value;
public Node left, right;
public boolean color;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}
private Node root;
private int size;
public RBTree(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 判断节点node的颜色
private boolean isRed(Node node){
if(node == null)
return BLACK;
return node.color;
}
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
// 左旋转
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
// 右旋转
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// 颜色翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
// 向红黑树中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 最终根节点为黑色节点
}
// 向以node为根的红黑树中插入元素(key, value)，递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value); // 默认插入红色节点
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);
if (isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
}
// 返回以node为根节点的二分搜索树中，key所在的节点
private Node getNode(Node node, K key){
if(node == null)
return null;
if(key.equals(node.key))
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
public boolean contains(K key){
return getNode(root, key) != null;
}
public V get(K key){
Node node = getNode(root, key);
return node == null ? null : node.value;
}
public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 从二分搜索树中删除键为key的节点
public V remove(K key){
Node node = getNode(root, key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove(node.left , key);
return node;
}
else if(key.compareTo(node.key) > 0 ){
node.right = remove(node.right, key);
return node;
}
else{ // key.compareTo(node.key) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 待删除节点右子树为空的情况
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
public static void main(String[] args){
System.out.println("Pride and Prejudice");
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words: " + words.size());
RBTree<String, Integer> map = new RBTree<>();
for (String word : words) {
if (map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}
System.out.println();
}
}
2-3树
特点
红黑树和2-3树
哈希表
哈希函数的设计
原则
一致性:如果a==b,hash(a)==hash(b)
解决哈希冲突
链表地址法
BitMap分析1
实现原理
在java中，一个int类型占32个比特，我们用一个int数组来表示时未new int[32],总计占用内存32*32bit,现假如我们用int字节码的每一位表示一个数字的话，那么32个数字只需要一个int类型所占内存空间大小就够了，这样在大数据量的情况下会节省很多内存。
具体思路:
1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:
tmp[0]:可表示0~31
tmp[1]:可表示32~63
tmp[2]可表示64~95
.......
那么接下来就看看十进制数如何转换为对应的bit位：
假设这40亿int数据为：6,3,8,32,36,......，那么具体的BitMap表示为：
如何判断int数字在tmp数组的哪个下标，这个其实可以通过直接除以32取整数部分，例如：整数8除以32取整等于0，那么8就在tmp[0]上。另外，我们如何知道了8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。
private long length;
private static int[] bitsMap;
private static final int[] BIT_VALUE = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000};
public BitMap2(long length) {
this.length = length;
/**
* 根据长度算出，所需数组大小
* 当 length%32=0 时大小等于
* = length/32
* 当 length%32>0 时大小等于
* = length/32+l
*/
bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
}
/**
* @param n 要被设置的值为n
*/
public void setN(long n) {
if (n < 0 || n > length) {
throw new IllegalArgumentException("length value "+n+" is illegal!");
}
// 求出该n所在bitMap的下标,等价于"n/5"
int index = (int) n>>5;
// 求出该值的偏移量(求余),等价于"n%32"
int offset = (int) n & 31;
/**
* 等价于
* int bits = bitsMap[index];
* bitsMap[index]=bits| BIT_VALUE[offset];
* 例如,n=3时,设置byte第4个位置为1 （从0开始计数，bitsMap[0]可代表的数为：0~31，从左到右每一个bit位表示一位数）
* bitsMap[0]=00000000 00000000 00000000 00000000 | 00000000 00000000 00000000 00001000=00000000 00000000 00000000 00000000 00001000
* 即: bitsMap[0]= 0 | 0x00000008 = 3
*
* 例如,n=4时,设置byte第5个位置为1
* bitsMap[0]=00000000 00000000 00000000 00001000 | 00000000 00000000 00000000 00010000=00000000 00000000 00000000 00000000 00011000
* 即: bitsMap[0]=3 | 0x00000010 = 12
*/
bitsMap[index] |= BIT_VALUE[offset];
}
/**
* 获取值N是否存在
* @return 1：存在，0：不存在
*/
public int isExist(long n) {
if (n < 0 || n > length) {
throw new IllegalArgumentException("length value illegal!");
}
int index = (int) n>>5;
int offset = (int) n & 31;
int bits = (int) bitsMap[index];
// System.out.println("n="+n+",index="+index+",offset="+offset+",bits="+Integer.toBinaryString(bitsMap[index]));
return ((bits & BIT_VALUE[offset])) >>> offset;
}
bitMap应用
看个小场景 > 在3亿个整数中找出不重复的整数，限制内存不足以容纳3亿个整数。
对于这种场景我可以采用2-BitMap来解决，即为每个整数分配2bit，用不同的0、1组合来标识特殊意思，如00表示此整数没有出现过，01表示出现一次，11表示出现过多次，就可以找出重复的整数了，其需要的内存空间是正常BitMap的2倍，为：3亿*2/8/1024/1024=71.5MB。
具体的过程如下：
扫描着3亿个整数，组BitMap，先查看BitMap中的对应位置，如果00则变成01，是01则变成11，是11则保持不变，当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。
已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99 999 999个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）
bitMap问题
BitMap 的思想在面试的时候还是可以用来解决不少问题的，然后在很多系统中也都会用到，算是一种不错的解决问题的思路。
但是 BitMap 也有一些局限，因此会有其它一些基于 BitMap 的算法出现来解决这些问题。
数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。
BitMap分析2
bitMap是位图，其实准确的来说，翻译成基于位的映射，举一个例子，有一个无序有界int数组{1,2,5,7},初步估计占用内存4*4=16字节，这倒是没什么奇怪的，但是假如有10亿个这样的数呢，10亿4字节/(1024 * 1024 * 1024)=3.72G左右（1GB=1024MB 、1MB=1024KB 、1KB=1024B 、1B=8b）。如果这样的一个大的数据做查找和排序，那估计内存也崩溃了，有人说，这些数据可以不用一次性加载，那就是要存盘了，存盘必然消耗IO。我们提倡的是高性能，这个方案直接不考虑。
问题分析
如果用BitMap思想来解决的话，就好很多，解决方案如下：
一个byte是占8个bit，如果每一个bit的值就是有或者没有，也就是二进制的0或者1，如果用bit的位置代表数组值有还是没有， 那么0代表该数值没有出现过，1代表该数组值出现过。不也能描述数据了吗？具体如下图：
现在假如10亿的数据所需的空间就是3.72G/32了吧，一个占用32bit的数据现在只占用了1bit，节省了不少的空间，排序就更不用说了，一切显得那么顺利。这样的数据之间没有关联性，要是读取的，你可以用多线程的方式去读取。时间复杂度方面也是O(Max/n)，其中Max为byte[]数组的大小，n为线程大小。
应用与代码实现
一个数怎么快速定位它的索引号，也就是说搞清楚byte[index]的index是多少，position是哪一位。举个例子吧，例如add(14)。14已经超出byte[0]的映射范围，在byte[1]范围之类。那么怎么快速定位它的索引呢。如果找到它的索引号，又怎么定位它的位置呢。Index(N)代表N的索引号，Position(N)代表N的所在的位置号。
Index(N) = N/8 = N >> 3;
Position(N) = N%8 = N & 0x07;
add(int num)
你要向bitmap里add数据该怎么办呢，不用担心，很简单，也很神奇。上面已经分析了，add的目的是为了将所在的位置从0变成1.其他位置不变.
public void add(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。
bits[arrayIndex] |= 1 << position;
}
clear(int num)
对1进行左移，然后取反，最后与byte[index]作与操作。
public void clear(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了.
bits[arrayIndex] &= ~(1 << position);
}
contain(int num)
public boolean contain(int num){ // num/8得到byte[]的index
int arrayIndex = num >> 3; // num%8得到在byte[index]的位置
int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可
return (bits[arrayIndex] & (1 << position)) !=0;
}
完整代码
public class BitMap {
//保存数据的
private byte[] bits;
//能够存储多少数据
private int capacity;
public BitMap(int capacity){
this.capacity = capacity;
//1bit能存储8个数据，那么capacity数据需要多少个bit呢，capacity/8+1,右移3位相当于除以8
bits = new byte[(capacity >>3 )+1];
}
public void add(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。
bits[arrayIndex] |= 1 << position;
}
public boolean contain(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可
return (bits[arrayIndex] & (1 << position)) !=0;
}
public void clear(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了.
bits[arrayIndex] &= ~(1 << position);
}
public static void main(String[] args) {
BitMap bitmap = new BitMap(100);
bitmap.add(7);
System.out.println("插入7成功");
boolean isexsit = bitmap.contain(7);
System.out.println("7是否存在:"+isexsit);
bitmap.clear(7);
isexsit = bitmap.contain(7);
System.out.println("7是否存在:"+isexsit);
}
}
稀疏位图
位图（bitmap／bitset）在工程中应用广泛（如搜索引擎中的posting list），同时也是面试中一个重要考点
位图在求交（introsect），求并（union）计算时有很好的性能，但如果数据集分布稀疏时，也会浪费较多空间。例如，当数据取值范围为[0, 2^32-1]，数据个数在1000w左右时，位图占用512MB，其中0的个数只占0.2%，空间浪费相当严重。
为了解决空间浪费，显然位图需要进行压缩。Daniel Lemire的Roaring Bitmaps是众多压缩（稀疏）位图实现中的性能最好的一种：
Roaring的数据结构
Roaring Bitmaps明确面向稀疏位图，使用之前你要明确数据的分布／数量，否则Roaring可能占用比未压缩位图更多的空间和耗费更多的操作时间。
Roaring Bitmaps思路是将取值范围分片，每片大小相同，可容纳2^16个数。根据范围内实际数据的个数／分布选择最紧凑的存储形式：
区间内数据连续分布，则选择用Run Length Encoding编码
Roaring将Bitmap从一层的连续存储，转换为一个二级的存储结构
第一层称之为Chunk，每个Chunk表示该区间取值范围的base(n2^16, 0<= n < 2^16)，如果该取值范围内没有数据则Chunk不会创建
第二层称之为Container，会依据数据分布进行创建（Container内的值实际是区间内的offset）
Roaring并不是一种静态数据结构，随着数据的增删，Container选择的存储格式也会随之自动调整
这里另一个重要参数是如何依据数据个数来判定使用位图还是数组。Roaring 选择4096作为阈值。
当区间内数量少于4096时，数组占用更紧凑；多于4096，则使用位图更经济
Roaring 提供O(logn)的查找性能：
首先二分查找key值的高16位是否在分片(chunk）中
如果分片存在，则查找分片对应的Container是否存在
如果Bitmap Container，查找性能是O(1)
Roaring的性能
Roaring使用了SIMD对操作进行了加速，但是SIMD是一门相当trick的技术，有机会可以单独再分析SIMD对性能的影响（尤其是introset／union）。
Lucene在5.0中引入了Roaring缓存filter，并对Roaring进行了性能评测，得到了一些有趣的结论。
遍历
当数据比较稀疏时，Roaring相比Bitmap性能更好，但弱于int数组
当数据比较密集时，Roaring性能会比Bitmap差，最好的是int数组
内存占用
数据极其稀疏时，int数组更节省空间，但到了某一拐点后，Roaring会更加节省空间
数据很密集时，int数组占用空间呈线性增长会快速超越Bitmap占用，而Roaring甚至可能由于其紧凑的编码格式（Run Length Encoding）反而比Bitmap更节省空间
构建时间
当数据极其稀疏时，位图构建速度远远快过int数组和Roaring
当数据超过全量1%时，Roaring成为构建速度更快的格式
skiplist
skiplist就是普通单向链表的基础上增加了分层索引，可以快速地根据分层索引定位数据。
查找
比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤:
从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1
然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0
在结点17上，level==0索引到19,查找完毕。
如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败
# Node节点
//forward declaration
template<typename K, typename V>
class SkipList;
template<typename K, typename V>
class Node {
friend class SkipList<K, V>;
public:
Node() {}
Node(K k, V v);
~Node();
K getKey() const;
V getValue() const;
private:
K key;
V value;
Node<K, V> **forward;
int nodeLevel;
};
template<typename K, typename V>
Node<K, V>::Node(const K k, const V v) {
key = k;
value = v;
};
template<typename K, typename V>
Node<K, V>::~Node() {
delete[]forward;
};
template<typename K, typename V>
K Node<K, V>::getKey() const {
return key;
}
template<typename K, typename V>
V Node<K, V>::getValue() const {
return value;
}
# 查找实现
template<typename K, typename V>
Node<K, V> *SkipList<K, V>::search(const K key) const {
Node<K, V> *node = header;
for (int i = level; i >= 0; --i) {
while ((node->forward[i])->key < key) {
node = *(node->forward + i);
}
}
node = node->forward[0];
if (node->key == key) {
return node;
} else {
return nullptr;
}
};
插入
其实插入节点的关键就是找到合适的插入位置，即从所有小于待插入节点key值的节点中，找出最大的那个，所以插入节点的过程如下:
查找合适的插入位置，比如上图中要插入key为17的结点，就需要一路查找到12,由于12 < 17,而12的下一个结点19 > 17,因而满足条件
创建新结点，并且产生一个在1~MAX_LEVEL之间的随机level值作为该结点的level
template<typename K, typename V>
bool SkipList<K, V>::insert(K key, V value) {
Node<K, V> *update[MAX_LEVEL];
Node<K, V> *node = header;
for (int i = level; i >= 0; --i) {
while ((node->forward[i])->key < key) {
node = node->forward[i];
}
update[i] = node;
}
//首个结点插入时，node->forward[0]其实就是footer
node = node->forward[0];
//如果key已存在，则直接返回false
if (node->key == key) {
return false;
}
int nodeLevel = getRandomLevel();
if (nodeLevel > level) {
nodeLevel = ++level;
update[nodeLevel] = header;
}
//创建新结点
Node<K, V> *newNode;
createNode(nodeLevel, newNode, key, value);
//调整forward指针
for (int i = nodeLevel; i >= 0; --i) {
node = update[i];
newNode->forward[i] = node->forward[i];
node->forward[i] = newNode;
}
++nodeCount;
#ifdef DEBUG
dumpAllNodes();
#endif
return true;
};
移除
template<typename K, typename V>
bool SkipList<K, V>::remove(K key, V &value) {
Node<K, V> *update[MAX_LEVEL];
Node<K, V> *node = header;
for (int i = level; i >= 0; --i) {
while ((node->forward[i])->key < key) {
node = node->forward[i];
}
update[i] = node;
}
node = node->forward[0];
//如果结点不存在就返回false
if (node->key != key) {
return false;
}
value = node->value;
for (int i = 0; i <= level; ++i) {
if (update[i]->forward[i] != node) {
break;
}
update[i]->forward[i] = node->forward[i];
}
//释放结点
delete node;
//更新level的值，因为有可能在移除一个结点之后，level值会发生变化，及时移除可避免造成空间浪费
while (level > 0 && header->forward[level] == footer) {
--level;
}
--nodeCount;
#ifdef DEBUG
dumpAllNodes();
#endif
return true;
};
