java - 使用 HashMap 将字符串转换为整数以优化空间使用

Question

我有一个程序可以从目录中的文本文件中读取单词。然后将这些单词存储到二叉搜索树中，以便在文件之间进行操作。但是，当文件很多并且文件太大时，Strings似乎占用了太多内存。我想通过将字符串转换为整数来优化空间，我相信 HashMap 可以帮助我实现这一目标，但我不知道该怎么做。具体来说，如果我有一个 HashMap 充当所有文件中所有不同单词的字典，我如何为它们分配不同的整数来帮助我创建平衡的二叉搜索树？

Answer 1

不幸的是，由于 HashMap 在 Java 中的实现方式，这不会节省您的空间。当您将值存储在 HashMap 中时， HashMap 实际上将记录存储为 Entry 对象，该对象同时存储值和键。因此，使用 HashMap 实际上不会阻止您引用这些大字符串，也不会在 BST 实现中节省内存。

键与值一起存储在 Entry 对象中的原因是完美的哈希函数(没有冲突的函数)对于现实世界计算机中的哈希表来说并不实用。如果哈希函数为每个输入分配一个唯一的哈希值，那么当您使用无界键空间(如字符串)时，它将需要无限量的内存来存储哈希表，因为会有无限数量的可能的地址偏移。

相反，真正的哈希表实现将数据存储在固定大小的数组中，并使用不完美的哈希函数(存在冲突的函数，即两个输入可以具有相同的哈希值)来分配内存位置，并将数组大小调整为空间开始得到利用。有多种策略可以处理这些冲突，例如探测、二级哈希函数或在每个内存位置存储链表，但所有这些方法都需要知道使用什么 key 来存储 Entry。

在 Java 中，HashMap 实现使用链表方法来处理冲突。当为某个键存储值时，该键将被散列以确定该 Entry 将被放置在哪个“存储桶”中。每个存储桶都是一个 Entry 对象的链接列表，并且该 Entry 将被添加到该列表的末尾。当您稍后检索该键的值时，会再次计算哈希值以告诉它要查找哪个存储桶。迭代链表节点，直到找到其键与搜索键匹配的条目。这样，当你在HashMap中存储东西时，Java需要存储String，并且不会节省内存。

您是否考虑过对代码进行分析以确保内存问题的原因确实如您所认为的那样？可能是其他原因，因此您应该在投入时间想出更复杂的实现来节省内存之前确定根本原因。有多种方法可以节省内存，但实现起来并不一定很简单，因此最好确保这些努力确实会对您有所帮助。