用java实现hashmap数据结构

Question

我有一个技术测试，问题陈述如下，我没有得到确切的我必须做什么，请帮助我同样通过提供一些样本代码。

Implement a hash-map data structure from scratch , where both key and value are of string data type.
The details of how a hash works can be found in Chapter 11 of the book "Introduction to
Algorithms" by Cormen, Leiserson, Rivest. You should also refer to Section 3.7 of "The
Algorithm Design Manual" by Steven Skiena. For the required hash-map implementation,
the following conditions hold true:
1. The key is made up of lower-case english alphabets only (a,b,c...z). It can be of any
length.
2. Values are of string data type.
3. The hash function to be used is the one given in Section 3.7 of Skiena.
4. Choose a suitable size of the hash-map, that is, the number of buckets. It should be
greater than 100.
4. Collisions will be resolved using Chaining. Doubly linked lists will be used to store
colliding entries.
You will have to implement the following operations on the hash-map:
a. Create an empty hash-map.
b. Insert a (key, value) pair into the hash-map.
c. Delete a (key) from the hash-map (if present).
d. Search for a (key) in the hash-map, and if present return its value. Else return null.

Thanks in advance.

Answer 1

我相信用英语解释HashMaps会更有帮助。

什么是HashMap?

HashMap是一种能够将某些键映射到特定值的数据结构。钥匙和价值可以是任何东西。例如，如果我正在制作一个游戏，我可能会将每个用户名链接到一个朋友列表，由一个字符串列表表示。

为什么使用HashMap?

与数组和链接列表相比，HashMaps对数据的提取要快得多。排序数组可以通过二进制搜索在O(log )中找到一个特定的值。但是，HashMap可以检查它是否包含O(1)中的特定键。所有的键都必须是唯一的。

HashMaps是如何工作的？

HashMaps在后台使用数组。数组中的每个元素都是另一个数据结构(通常是链接列表或二进制搜索树)。HashMap在键上使用一个函数来确定将键的值放在数组中的位置。例如，如果我的HashMap接受Strings...possible哈希函数，则可以是：

A. Return the ASCII value of the first letter.
B. Return the sum of the ASCII values of every character in the String.
C. Return the ASCII value of the last character in the String.

返回的值将确定该值进入数组的索引。

，但是等等！有个问题！

返回的值有可能超出数组的界限。因此，我们应该用数组长度对返回的值进行建模。

return Math.abs(number%hashMapArray.length);

碰撞：

多个键不可能使哈希函数生成相同的索引吗？是。例如，如果我们在strings...any的哈希映射中使用上面显示的第一个散列函数，两个以相同字母开头的字符串将被赋予相同的数组索引。

这叫做碰撞。

我们如何处理碰撞？

一种碰撞处理技术称为链。由于数组中的每个元素都是一个链接列表(或类似的数据结构)，具有相同哈希值的多个键将放置在相同的链接列表或“桶”中。之后，哈希映射可以通过使用散列函数计算哈希代码并搜索特定的链接列表来检索值，以查看它是否包含具有相同键的值。

为了避免冲突，必须编写一个好的散列函数。

链接的优势：

-Array不能溢出

-Data可以很容易地移除

链接的缺点：

如果存储桶包含很长的链接列表，则会影响-May的性能。

桶数的条目总数称为负载因子。如果负载系数太低，就会浪费大量的空间。如果负载因子太高，哈希的优势就会丧失。负载因子的一个很好的折衷方案是.75。