datastructure

发表于 | 更新于:

常规数据结构

本文总结自 数据结构与算法-js实现
数据结构：用来组织数据的结构，方法无非是查找、增加、移除；

常见结构

  1. array：长度固定，使用 index 进行操作
    方法：push()；pop()-移除索引值最大的元素；
  2. LinkedList：增加删除很方便，连接查找不方便
    在计算机科学中, 一个 链表 是数据元素的线性集合。在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。
    方法：prepend(value)；append(value)；delete(value)；find；reverse；
  3. doubly linkedlist：双向链表：每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。 方法：与链表结构一样
  4. queue：队列基本操作有两种:向队列的后端位置添加实体，称为入队；从队列的前端位置移除实体，称为出队。FIFO
    方法：入队enqueue(value)；出队dequeue()；peek()访问结构中的当前元素（不删除）
  5. stack：栈基本操作有两种:push, 添加元素到栈的顶端；pop, 移除栈最顶端的元素。LIFO
    方法：push(value)；pop()；peek()
  6. HashTable：依赖LinkedList，哈希表(hashtable 或hashmap) 是一种实现 关联数组(associative array) 的抽象数据；该结构可以将 键映射到值。 （mps：实现了数组没有的取值方式）
    哈希表使用哈希函数/散列函数来计算一个键在数组或桶(buckets)或槽(slots)中对应的索引,可使用该索引找到所需的值。 理想情况下,散列函数将为每个键分配给一个唯一的桶(bucket)索引,但是大多数哈希表设计采用不完美的散列函数,这可能会导致”哈希冲突(
    hash collisions)”,也就是散列函数为多个键(key)生成了相同的索引,这种碰撞必须 以某种方式进行处理（可以类比柳条，柳叶；）。
    方法：hash(key)–散列函数；set(key, value)–保存是带有key，做防重复处理； delete(key)
    ；get(key)；has(key)；getKeys()；
  7. heap：（直接使用数组存储数据）在计算机科学中, 一个 堆(heap) 是一种特殊的基于树的数据结构。分为两种堆，在一个最小堆(min heap) 中, 如果p是c的一个父级节点, 那么p的key(或value)
    应小于或等于c的对应值；在一个最大堆(max heap) 中,p的key(或value)大于c的对应值（都不关心同层级的左右节点间的大小关系）。最大最小维护了所有支点到根节点链路上的递增递减关系。
    方法：add()；remove()；find()；peek()；poll()-返回堆最顶端的元素（会调整整个结构）；swap(
    indexOne, indexTwo)；heapifyUp(customStartIndex)-从尾巴开始整理树；heapifyDown(customStartIndex = 0)-从顶端开始整理树；index(),has(),element() -基于index操作。
  8. priority queue：优先队列通常用堆来实现，每个元素都有与之关联的优先级。
    二叉树：每个节点分左右子节点的树。二叉树常被用于实现二叉查找树和二叉堆。
  9. BinaryTreeNode：二叉树，分治思想，递归，双向链表。
    • BinarySearchTree：二叉查找树（BST），并且每个节点的值都大于等于其左子树中的所有节点的值而小于等于右子树的所有节点的值（sorted binary trees）。 BST有一个重要性质，就是它的中序遍历结果递增排序。remove()方法是关键。（根据任意两个节点的高度（索引）可以判断大小关系？这里使用的链表结构）
    • AvlTree：继承自 BST，self-balancing binary search tree。balance()方法与balanceFactor属性（最终看子节点层级）。
    • RedBlackTree：继承自 BST，self-balancing binary search tree。平衡的实现没去理解。

B站红黑树实战
红黑树的约束

  • 节点不是红色就是黑色；
  • 根节点是黑色，叶节点是不存储数据的黑色空节点；
  • 红红节点不能相连；
  • 新插入的节点都是红色；

新增节点后的三种操作

  1. 节点颜色变化
    • 场景：父节点，叔叔节点都是红色；
    • 操作：父节点，叔叔节点设为黑色，祖父节点设为红色；
  2. 左旋：
    • 场景：父节点是红色，叔叔节点是黑色，当前节点是右子树；
    • 操作：父节点逆时针旋转，左子树变成“另一个节点”的右子树；
  3. 右旋：
    • 场景：父节点是红色，叔叔节点是黑色，当前节点是左子树；
    • 操作：父节点顺时针旋转，右子树变成“另一个节点”的右子树；

Big O Notation

Big O notation (最大复杂度)is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On
the chart below you may find most common orders of growth of algorithms specified in Big O notation.

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

Big O Notation Computations for 10 elements Computations for 100 elements Computations for 1000 elements
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

Data Structure Operations Complexity

Data Structure Access Search Insertion Deletion Comments
Array 1 n n n
Stack n n 1 1
Queue n n 1 1
Linked List n n 1 n
Hash Table - n n n In case of perfect hash function costs would be O(1)
Binary Search Tree n n n n In case of balanced tree costs would be O(log(n))
B-Tree log(n) log(n) log(n) log(n)
Red-Black Tree log(n) log(n) log(n) log(n)
AVL Tree log(n) log(n) log(n) log(n)
Bloom Filter - 1 1 - False positives are possible while searching

算法分析指标

算法的复杂性体现在运行该算法时所需的计算机资源多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。

  • 时间复杂度：是指执行算法所需要的计算工作量；
  • 空间复杂度：是指执行这个算法所需要的内存空间。

java 容器实战

HashMap

LinkedHashMap：LinkedHashMap是HashMap的一个子类，记录了的插入顺序。
TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序。
结构的设计：那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

put 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤①：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤③：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 步骤④：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤⑤：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);
                    break;
                }
                 // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
						break;
                p = e;
             }
        }
        
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    // 步骤⑥：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes"，"unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
               else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 链表优化重hash的代码块
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                       loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1.8的优化

确定哈希桶数组索引位置时：优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
扩容操作时：1.7使用了单链表的头插入方式，1.8单链表的尾插入？；不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了。
链表长度大于8时，链表结构转红黑树。

spring 容器实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
AbstractApplicationContext
/** ApplicationEvents published early */
private Set<ApplicationEvent> earlyApplicationEvents;
/** BeanFactoryPostProcessors to apply on refresh */
private final List<BeanFactoryPostProcessor> beanFactoryPostProcessors = new ArrayList<BeanFactoryPostProcessor>();

DefaultSingletonBeanRegistry
/** Cache of singleton objects: bean name --> bean instance */
private final Map<String, Object> singletonObjects = new ConcurrentHashMap<String, Object>(256);
/** Disposable bean instances: bean name --> disposable instance */
private final Map<String, Object> disposableBeans = new LinkedHashMap<String, Object>();
/** Map between dependent bean names: bean name --> Set of dependent（依赖他人者） bean names */
private final Map<String, Set<String>> dependentBeanMap = new ConcurrentHashMap<String, Set<String>>(64);
/** Cache of singleton factories: bean name --> ObjectFactory */
private final Map<String, ObjectFactory<?>> singletonFactories = new HashMap<String, ObjectFactory<?>>(16);
/** Cache of early singleton objects: bean name --> bean instance */
private final Map<String, Object> earlySingletonObjects = new HashMap<String, Object>(16);
/** Set of registered singletons, containing the bean names in registration order; getSingleton() # addSingleton()*/
private final Set<String> registeredSingletons = new LinkedHashSet<String>(256);

DefaultListableBeanFactory
/** List of names of manually registered singletons（spring 手动注册）, in registration order */
private volatile Set<String> manualSingletonNames = new LinkedHashSet<String>(16);
/** List of bean definition names, in registration order */
private volatile List<String> beanDefinitionNames = new ArrayList<String>(256);
/** Map of bean definition objects, keyed by bean name */
private final Map<String, BeanDefinition> beanDefinitionMap = new ConcurrentHashMap<String, BeanDefinition>(256);

AbstractBeanFactory
/** BeanPostProcessors to apply in createBean */
private final List<BeanPostProcessor> beanPostProcessors = new ArrayList<BeanPostProcessor>();

AbstractAutowireCapableBeanFactory
/**
 * Dependency interfaces to ignore on dependency check and autowire, as Set of
 * Class objects. By default, only the BeanFactory interface is ignored.
 */
private final Set<Class<?>> ignoredDependencyInterfaces = new HashSet<Class<?>>();