【Data Structure】哈希表（Hash table）

哈希表（Hash table）

哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数（Hash function），存放元素的数组称做散列表（Hash table）。

...

Posted by Wei on 2019-05-30, Last Modified on 2025-04-23

【Data Structure】常用数据结构的时间复杂度

常用数据结构的时间复杂度

Data Structure	Add	Find	Delete	GetByIndex
Array (T[])	O(n)	O(n)	O(n)	O(1)
Linked list (LinkedList)	O(1)	O(n)	O(n)	O(n)
Resizable array list (List)	O(1)	O(n)	O(n)	O(1)
Stack (Stack)	O(1)	-	O(1)	-
Queue (Queue)	O(1)	-	O(1)	-
Hash table (Dictionary)	O(1)	O(1)	O(1)	-
Tree-based dictionary (SortedDictionary<K,T>)	O(log n)	O(log n)	O(log n)	-
Hash table based set (HashSet)	O(1)	O(1)	O(1)	-
Tree based set (SortedSet)	O(log n)	O(log n)	O(log n)	-

...

Posted by Wei on 2019-05-30, Last Modified on 2023-09-02

【Data Structure】哈夫曼树（Huffman Tree）

背景

在了解赫夫曼树之前，我们首先先介绍一些基础概念。

路径

路径是指在一棵树中，从一个节点到另一个节点之间的分支构成的通路。

...

Posted by Wei on 2019-05-30, Last Modified on 2023-02-21

【Data Structure】平衡二叉查找树（Balanced Binary Search Tree） - 红黑树（Red-Black Tree）

红黑树（Red-Black Tree）

在 1972 年，慕尼黑理工大学（Technical University of Munich）的计算机科学家 Rudolf Bayer 创造了**红黑树（Red-Black Tree）**数据结构。

除了包含数据和左右孩子节点之外，红黑树的节点还包含了一项特别的信息 – 颜色。这个颜色只包含两种颜色，即红色和黑色。

...

Posted by Wei on 2019-05-30, Last Modified on 2025-04-04

【Data Structure】平衡二叉查找树（Balanced Binary Search Tree） - AVL树

AVL 树

在 1962 年，俄罗斯数学家 G. M. Andel’son-Vel-skii 和 E. M. Landis 发明了第一种自平衡二叉查找树，叫做 AVL 树。AVL 树必须维持如下平衡条件，对每个节点 n：节点 n 的左子树的高度与右子树的高度的差至多是 1。

...