哈希表疑问

有两个疑问

1) 哈希表和二分搜索树中的映射有关系吗?

所谓的均匀, 是指哈希索引分布到空间上不能太大或者太小?

源自：哈希表和 SQRT 分解 1-1 哈希表基础

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-05-20 14:10:42

1）

映射是一种抽象数据结构，我们使用哈希表也能实现映射，使用二分搜索树也能实现映射。

对应到 Java 中，哈希表实现的映射是 HashMap，二分搜索树（红黑树）实现的映射是 TreeMap

2）

指哈希值均匀的分布在空间中。

比如 0-99 之间。10 20 30 40 50 60 70 80 90，就比 1， 2，3， 4， 5， 6，7， 98， 99 要均匀。

继续加油！：）

蓝色的sola 提问者 #1

第二问题中,我还没理解为什么要分布均匀?

2021-05-20 17:21:36
liuyubobobo 回复提问者蓝色的sola #2

分布不均匀哈希冲突大呀。同样一百个元素，极端情况下，分布绝对均匀，每个位置只有一个元素；分布绝对不均匀，一个位置有 100 个元素，不但浪费空间，查找一个元素的时间性能开销也大。

2021-05-21 05:20:26