问题标签 [hashmap]

我有一百万行 .txt 格式的数据。格式非常简单。对于每一行：

你知道我的意思。对于每个用户，它可能出现多次，或者只出现一次（你永远不知道）。我需要找出每个用户的所有值。因为用户可能随机出现，所以我使用 Hashmap 来做。即：HashMap(key: String, value: ArrayList)。但是要向arrayList添加数据，我必须不断地使用HashMap get(key)来获取arrayList，给它添加值，然后把它放回HashMap。我觉得效率不是很高。有人知道更好的方法吗？

在我的代码中，我默认对所有列表使用 ArrayList，对所有映射使用 HashMap，对所有集合使用 HashSet。

从实际的角度来看，由于选择了错误的实现，我在灵活性、可扩展性、可读性和性能方面损失了多少？什么时候花时间决定使用一个而不是另一个有意义？

我当然看到了一个非常明确的案例，说明为什么在某些情况下有人会使用 LinkedList 而不是 ArrayList。什么时候有人觉得使用 HashMap 而不是 TreeMap 或 HashTable 很重要？套装呢？

问题：

1. 选择不当的代价是什么？
2. 有没有人有关于选择错误的实施和数据中心着火的灾难故事？
3. 有什么好的经验法则吗？
4. 有没有你不能没有的晦涩的集合实现？

我已通读：

• https://docs.oracle.com/javase/1.5.0/docs/api/java/util/TreeMap.html
• https://docs.oracle.com/javase/1.5.0/docs/api/java/util/HashMap.html
• Java：List 的 ArrayList、Map 的 HashMap 和 Set 的 HashSet？ ETC...

我发现从理论的角度来看这个问题是相关的，但我对现实世界更感兴趣，在战壕中回答。

我已经看到一些关于 SO re Java hashmaps 及其O(1)查找时间的有趣声明。有人可以解释为什么会这样吗？除非这些哈希图与我购买的任何哈希算法有很大不同，否则必须始终存在包含冲突的数据集。

在这种情况下，查找将是O(n)而不是O(1).

有人可以解释他们是否是O(1)，如果是，他们是如何实现的？

我在 C# 中经常使用 HashSet 和 Dictionary，发现它们非常快......

我试过使用 std::map 和 std::hash_map 并且发现它们比较慢。这听起来像预期的行为吗？我在使用 std::hash_map 时可能做错了什么？

或者，那里有更好的 C++ Hash 容器吗？

我正在散列 int32，通常大约 100,000 个。

更新：我用 C# 和 C++ 创建了一个 repro。它运行了两次试验，它们在 C# 中需要 19 毫秒和 13 毫秒，在 C++ 中大约需要 11,000 毫秒。我的 C++ 代码一定有什么问题 :)

（两者都作为发布版本运行，都是控制台应用程序）

C# 输出：

C++ 输出：

C++ 输出（使用 stdext::hash_map 而不是 std::map）

C++ 输出（使用 stdext::hash_map，x64 版本）

笔记：

• Set2 并没有像我在 C++ 中想要的那样被填充，我希望它与 Set1 有 50% 的交集（就像在 C# 中一样），但是出于某种原因我不得不将我的随机数乘以 10 甚至让它们部分不相交

C＃：

C++：

您认为使用字节数组作为 Map 键有什么问题吗？我也可以做new String(byte[])和散列，String但使用起来更简单byte[]。

使用 STL C++ hash_map...

像这样...

我收到一大堆错误。这是前三个...

错误 1 ​​错误 C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : 无法推断出 'const std::_Tree<_Traits> 的模板参数&' 来自 'const MyKeyObject' c:\program files\microsoft visual studio 8\vc\include\functional 143

错误 2 错误 C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : 无法推断 'const std::basic_string<_Elem,_Traits, _Alloc> &' 来自 'const Tasking::MyKeyObject' c:\program files\microsoft visual studio 8\vc\include\functional 143

错误 3 错误 C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : 无法从 'const MyDataObject' c 推导出 'const _Elem *' 的模板参数:\程序文件\微软视觉工作室 8\vc\include\functional 143

...

如果我将键设置为像 int 这样简单的东西，一切都很好。

我究竟做错了什么？！也许我需要用模板做点什么？

有没有更好（更快？）的方式来使用这样的自定义键对象访问数据？

迭代 a 中的项目的最佳方法是HashMap什么？

运行以下类时，ExecutionService 经常会死锁。

那么为什么会这样呢？或者更好 - 我如何编写测试以确保自定义抽象映射的实现是线程安全的？（一些实现有多个映射，另一个代表缓存实现等）

一些背景知识：这发生在 Windows 上的 Java 1.6.0_04 和 1.6.0_07 下。我知道问题来自 sun.misc.Unsafe.park()：

• 我可以在我的 Core2 Duo 2.4Ghz 笔记本电脑上重现该问题，但在调试运行时无法重现
• 我可以在工作时在我的 Core2 Quad 上进行调试，但我已经将它挂在 RDP 上，所以直到明天才能获得堆栈跟踪

下面的大多数答案都是关于 HashMap 的非线程安全性，但我在 HashMap 中找不到任何锁定的线程——它都在 ExecutionService 代码（和 Unsafe.park()）中。明天我将仔细检查这些线。

这一切都是因为自定义抽象 Map 实现不是线程安全的，所以我着手确保所有实现都是线程安全的。从本质上讲，我想确保我对 ConcurrentHashMap 等的理解正是我所期望的，但发现 ExecutionService 奇怪地缺乏......

我需要将 python 代码转换为等效的 java 代码。Python 通过提供许多快捷功能使开发人员的生活变得非常轻松。但现在我需要将其迁移到 Java。我想知道 java 中 dict 对象的等价物是什么？我尝试过使用 HashMap，但生活就是地狱。对于初学者来说，考虑到这一点，

那么如何将它转换成Java呢？对于初学者，我使用了 HashMap 对象，

我的问题是获取包含名称和强度的列表部分，然后更新强度部分。有没有可行的方法来做到这一点？我应该考虑一些不同的数据结构吗？请帮忙。

我经常使用 IntelliJ IDEA 自动生成一个类的hashCode()方法，通常该方法采用以下形式：

我的问题是乘以 31 的目的是什么？我知道这是一个质数，但为什么要专门选择 31？此外，如果hashCode()为一个特别小/大的数据集实现一个，人们会以不同的方式解决这个问题吗？