RedBlackTree.e
(25.29 KB, 下载次数: 86)
RedBlackTree.e
(25.29 KB, 下载次数: 86)
易造轮 发表于 2023-5-9 04:26
请教哈希表用的是哪种查找？
哈希表是通过哈希函数将每个键映射到唯一的数组索引位置上，并将键值对存储在该位置上。查找时只需要使用同样的哈希函数找到对应的索引位置，并访问该位置上的键值对。在不考虑冲突的情况，查找的时间复杂度为 O(1)。
然而，实际应用中，并不能完美地将所有的键均匀地分散在整个哈希表中，有时候会出现多个键映射到同一个索引位置的情况，这种情况称为哈希冲突。为了解决哈希冲突，哈希表通常采用链表或者红黑树等数据结构来存储在同一个索引位置上的多个键值对，这样每次查找时需要依次遍历链表或者红黑树，查找时间复杂度为O(n/k)，其中k为哈希表的容量，n为存储在哈希表中的键值对数量。
可以称为哈希树（Hash Tree），是在红黑树的基础上添加哈希函数，但本质上还是红黑树。
哈希表是通过哈希函数将键映射到数组索引中。哈希树则是通过哈希函数计算后作为键，并按照二叉搜索树的规则组织起来。
在不考虑哈希冲突的情况，哈希表的时间复杂度为 O(1)，哈希树的时间复杂度为 O(log n)。哈希表在简单数据的情况优于哈希树。但在复杂数据的情况哈希树可能更有优势。
哈希表会对哈希值进行求余数操作，并限制在哈希表的容量内，更容易发生哈希冲突。而哈希树更高效，不需要进行求余数操作，哈希值可以为任意值，也因此哈希冲突的概率更小。
哈希表需要一个足够大的数组，大小通常是元素数量的几倍，而且也不一定能完美地将所有的键均匀地分散在整个哈希表中，所以会占用更多内存。哈希树占用的内存是根据节点的数量，因此占用的内存更少。
RedBlackTree.e
(34.61 KB, 下载次数: 22)
| 欢迎光临 精易论坛 (https://125.confly.eu.org/) | Powered by Discuz! X3.4 |