1. 首页
  2. 问答
  3. Java：地图中的内部数据结构

Java：地图中的内部数据结构

2010-07-15 53 views
4

我想创建一个实现Map接口的类。所以我正在编写代码来检查调用对象是否为空。不过，我对我应该在内部使用哪种数据结构有点困惑。目前我正在使用哈希表。 在此先感谢Java：地图中的内部数据结构

来源

2010-07-15 Rohan

回答

4

从Wikipedia，

关联数组通常用于 时查找是最常见的 操作。出于这个原因， 实现通常设计 以实现快速的查找，牺牲较慢插入 和比其它数据 结构（如协会 列表）的较大 存储足迹。

高效表示：
主要有两种有效的数据用于表示 关联数组，哈希表和 的平衡树 （ 结构，诸如红 - 黑树或AVL 树）。跳过列表也是 的替代方案，虽然相对较新并且没有被广泛使用的 。还可以使用B树（和 变体），并且当关联 阵列太大而不能在内存中完全驻留 时，例如在简单的 数据库中，通常使用B树（和 变体）。相对优势和 缺点包括：

  1. 渐近运行性能：哈希表有更快的平均查找 和插入时间，O（1），相比 平衡二叉搜索树的Θ（日志 N），而与Θ（n）相比，平衡树具有更快的最坏情况查找和插入时间 O（log n）。跳过 列表具有O（n）最差情况和O（log n）平均情况下的操作时间，但 具有较少的插入和删除 实际开销比平衡 二叉树。

  2. 订购保鲜：平衡二叉树和跳表保存 排序 - 允许一个有效 遍历键，以便或者 有效地定位关联 其主要是最近的给定值。 哈希表不保留订购 ，因此无法有效执行这些操作（它们的 要求数据在 单独的步骤中进行排序）。

  3. 范围查询：平衡二叉树可以很容易地适应 有效的单个值分配给键的 大范围有序，或者 计数以有序 范围的键的数目。 （对于数组 中的n个元素并在连续的m个密钥范围上执行操作，平衡的二叉树将花费O（log（n）+ m）时间 ，而散列表将需要Θ（n） 因为它需要搜索整个 表时间）

  4. 分配行为：用开寻址存储哈希表中 所有数据的存储器 不经常重新分配一个大的连续的块， 而树的分配执行许多 小，频繁分配。其结果 哈希表可能难以 分配在分段的堆，并 相反地树木可能导致堆 碎片。树也更容易 分配器的低效率 。紧凑性：散列表可以具有更小的存储空间，用于小值 类型，特别是当值为 位时。

  5. 持久性：有简单的持久版本的平衡二进制 树，在功能语言中尤其突出 。

  6. 支持新的密钥类型：建立一个哈希表需要的密钥类型，其中 可能很难写不好一个合理 哈希函数，而 平衡二叉树和跳表 只需要在总体排序 键。

有时简单 一个数据结构或其它的实施方式中具有 缺点可由 更好的设计来克服。例如：使用不受信任的输入作为键可能易受 其中一个 不可信用户提供数据旨在 以产生大量的 碰撞拒绝服务攻击

  • 哈希表。这可以通过 随机从 选择哈希函数的通用家庭，或通过散列 不可信的输入用插入之前加密 散列函数来克服。

  • 简单的平衡树浪费指针和分配 元空间;这些问题可以通过在每个节点中存储多个 元素并通过使用 内存池得到缓解。

来源

2010-07-15 05:59:20 missingfaktor

2

除了表格本身，您还可以维护一个整数成员变量来跟踪集合的大小，每次放入新的映射时递增一次，每次删除时递减一次。通过这种方式，可以简化size和isEmpty接口方法：

public int size() { 
    return this.size; 
} 

public boolean isEmpty() { 
    return this.size == 0; 
}

来源

2010-07-15 04:47:20 maerics

相关问题

 相关问题