压缩字典树 (Radix Trie/Patricia Trie) 深度解析
压缩字典树 (Compressed Trie),也常被称为 基数树 (Radix Trie) 或 Patricia Trie (Practical Algorithm to Retrieve Information Coded in Alphanumeric),是一种经过优化的字典树 (Trie) 数据结构。它在标准字典树的基础上,通过合并那些路径上只有一个子节点的节点,显著提高了空间效率,尤其适用于存储具有长公共前缀的字符串集合。 核心思想:标准字典树的每个节点通常只存储一个字符。当路径上出现连续的单子节点时,这些节点可以被合并成一个节点,该节点存储一个字符串片段。这样既能保持字典树的快速前缀查找能力,又能大幅减少节点数量和内存占用。 一、标准字典树 (Trie) 概述及其局限性在深入压缩字典树之前,我们先回顾一下标准字典树 (Trie) 的基本概念。 1.1 标准字典树 (Trie) 定义:Trie 是一种树形数据结构,用于存储字符串集合。它的名称来源于 “retrieval”,意为检索。 结构: 根节点通常为空字符串。 每个节点表示一个字符。 从根节点到任意节点的路...
哈希表负载因子详解(Load Factor)
哈希表 (Hash Table) 是一种高效的数据结构,用于存储键值对 (key-value pairs),提供快速的查找、插入和删除操作。它的核心思想是利用哈希函数 (Hash Function) 将键映射到数组的某个索引位置。然而,哈希表的性能高度依赖于负载因子 (Load Factor) 的管理,它在空间利用率、查找效率和再哈希 (Resizing/Rehashing) 成本之间扮演着关键的平衡角色。 核心思想:负载因子衡量了哈希表的“满”程度,是决定何时以及如何调整哈希表大小的关键指标,直接影响其性能和资源消耗。 一、哈希表简介与冲突在深入了解负载因子之前,我们先回顾哈希表的基本概念和冲突问题。 1.1 哈希表工作原理哈希表使用一个数组(通常称为桶数组或槽数组)来存储数据。当需要插入一个键值对时: 哈希函数:对键进行哈希计算,得到一个哈希值。 取模运算:将哈希值与桶数组的长度取模,得到一个数组索引。 存储:将键值对存储到该索引位置。 1.2 哈希冲突 (Hash Collision)不同的键经过哈希函数计算后,可能会得到相同的哈希值,进而映射到桶数组...
哈希表(Hash Table)原理详解
哈希表(Hash Table),又称散列表,是一种根据键(Key)直接访问存储位置的数据结构。它通过哈希函数将键映射到表中的一个位置来访问记录,从而实现平均 O(1) 时间复杂度的查找、插入和删除操作。哈希表是计算机科学中最重要的数据结构之一,广泛应用于数据库索引、缓存、符号表、唯一性检查等多种场景。 核心思想:哈希表通过哈希函数将任意大小的键映射到固定大小的数组索引,以实现快速的数据存取。 一、哈希表的基本概念哈希表的核心思想是键值映射。它将用户提供的键(key)通过一个特定的函数(哈希函数)转换成一个整数,这个整数就是数据在底层数组中的索引(下标)。 键 (Key): 唯一的标识符,用于查找、插入和删除数据。 值 (Value): 与键关联的数据。 哈希函数 (Hash Function): 将键映射到数组索引的函数。 哈希值 (Hash Value 或 Hash Code): 哈希函数计算出的整数值。 桶/槽 (Bucket/Slot): 底层数组中的一个位置,用于存储键值对。 示意图:哈希表基本概念 12345678910111213141...
