1. 哈希映射（Hash Map）
简介
哈希映射是一种基于哈希函数的数据结构，提供高效的键值存储。
Python算法
6 种常用自定义数据结构设计与实现技巧
本文详细介绍了哈希映射、双向链表、树状数组、LRU 缓存、并查集和跳表六种常见自定义数据结构。通过访问分析、设计技巧及 Python 代码示例，阐述了各结构的适用场景与性能特点。同时总结了包括选择合适结构、避免冗余、分层设计等在内的十大设计原则，助力开发者优化系统性能与可维护性。
本文详细介绍了哈希映射、双向链表、树状数组、LRU 缓存、并查集和跳表六种常见自定义数据结构。通过访问分析、设计技巧及 Python 代码示例，阐述了各结构的适用场景与性能特点。同时总结了包括选择合适结构、避免冗余、分层设计等在内的十大设计原则，助力开发者优化系统性能与可维护性。
哈希映射是一种基于哈希函数的数据结构，提供高效的键值存储。
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
| 搜索 | O(1) | O(n) |
class HashMap:
def __init__(self, size=100):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
pair[1] = value
return
self.table[index].append([key, value])
def get(self, key):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
return None
def remove(self, key):
index = self._hash(key)
self.table[index] = [pair for pair in self.table[index] if pair[0] != key]
双向链表是链表的一种扩展，每个节点包含前后两个指针。
| 操作 | 时间复杂度 |
|---|---|
| 插入 | O(1) |
| 删除 | O(1) |
| 搜索 | O(n) |
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def remove(self, data):
cur = self.head
while cur:
if cur.data == data:
if cur.prev:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
if cur == self.head:
self.head = cur.next
if cur == self.tail:
self.tail = cur.prev
break
cur = cur.next
用于处理前缀和查询，常用于动态数据统计。
| 操作 | 时间复杂度 |
|---|---|
| 更新 | O(log n) |
| 查询前缀和 | O(log n) |
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index, value):
while index <= self.size:
self.tree[index] += value
index += index & -index
def query(self, index):
sum_val = 0
while index > 0:
sum_val += self.tree[index]
index -= index & -index
return sum_val
用于管理有限缓存，最少使用的项被移除。
| 操作 | 时间复杂度 |
|---|---|
| 插入/访问 | O(1) |
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
用于动态连通性问题，如网络连接。
| 操作 | 时间复杂度 |
|---|---|
| 合并 | O(α(n)) |
| 查询 | O(α(n)) |
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_x] = root_y
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_y] += 1
用于有序数据的高效查询，替代平衡树。
| 操作 | 时间复杂度 |
|---|---|
| 插入 | O(log n) |
| 删除 | O(log n) |
| 查询 | O(log n) |
在进行数据结构设计时，有几个技巧可以帮助提高系统的效率、可维护性和扩展性。以下是一些常用的技巧：
通过合理运用这些设计技巧，可以帮助你在构建系统时优化性能、提高系统的可维护性和可扩展性。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online