Zomato面试体验|第1组（校外）-yiteyi-C++库

所有的数据结构都有自己的特点，例如，当需要快速搜索元素（在日志（n）中）时，使用BST。当需要在固定时间内获取最小或最大元素时，使用堆或优先级队列。类似地，哈希表用于在固定时间内获取、添加和删除元素。在进入实现方面之前，任何人都必须清楚哈希表的工作。下面是关于哈希表工作的简要背景，还应该注意，我们将交替使用哈希表和哈希表术语，尽管在Java中，哈希表是线程安全的，而哈希表不是。

null

我们将要实现的代码可以在链接1 和链接2

但强烈建议大家必须完整阅读本博客，尝试破解实现哈希映射的细节，然后尝试自己编写代码。

出身背景

每个哈希表都以（键、值）组合的形式存储数据。有趣的是，哈希表中的每个键都是唯一的，但值可以重复，这意味着对于其中存在的不同键，值可以相同。现在，当我们在数组中观察以获取值时，我们提供了与该数组中的值对应的位置/索引。在哈希表中，我们使用一个键来获取与该键对应的值，而不是索引。下面介绍整个过程

每次生成密钥时。密钥被传递给哈希函数。每个哈希函数都有两个部分 哈希代码和压缩器 .

哈希代码是一个整数 （随机或非随机）。在Java中，每个对象都有自己的哈希代码。我们将在哈希函数中使用JVM生成的哈希代码，并将哈希代码按哈希表的大小进行模数（%）压缩。 所以模算子是 A. 在我们的实现中。

整个过程确保，对于任何键，我们都会在哈希表大小内获得一个整数位置，以插入相应的值。

因此，这个过程很简单，用户给出一个（键，值）对集作为输入，并根据哈希函数生成的值生成一个索引，以存储与特定键对应的值。所以，每当我们需要获取一个对应于键的值时，这就是O（1）。

当哈希冲突的概念被引入时，这幅图就不再那么美好和完美了。想象一下，对于不同的键值，哈希表的同一块现在被分配到了它们之前存储与其他键值对应的值的位置。我们当然不能取代它。那将是灾难性的！为了解决这个问题，我们将使用分离链接技术，请注意，还有其他开放寻址技术，如双重哈希和线性探测，其效率几乎与分离链接相同，您可以在链接1 链接2 链接3

现在我们要做的是创建一个链表，对应于哈希表的特定bucket，以容纳对应于映射到同一bucket的不同键的所有值。

图片[1]-Zomato面试体验|第1组（校外）-yiteyi-C++库

现在可能会出现这样一种情况：所有键都映射到同一个bucket，我们从一个bucket得到一个大小为n（哈希表大小）的链表，而所有其他bucket都为空，这是最坏的情况，其中哈希表充当链表，搜索为O（n）。那我们该怎么办？

负荷系数

如果n是我们最初决定填充的桶的总数，比如说10个，假设其中7个已经填充，那么负载系数是7/10=0.7。

在我们的实施中 每当我们向哈希表中添加一个键值对时，我们都会检查负载因子，如果它大于0.7，我们就会将哈希表的大小增加一倍。

实施

散列节点数据类型

我们将尝试在不限制键和值的数据类型的情况下创建通用映射。此外，每个散列节点都需要知道它在链表中指向的下一个节点，因此还需要下一个指针。

我们计划保留在散列图中的函数是

获取（K键） ：如果密钥存在于中，则返回与该密钥对应的值 HT ( H 阿斯特 T （有能力）
getSize（） ：返回HT的大小
添加（） ：将新的有效密钥、值对添加到HT，如果已经存在，则更新值
删除（） ：删除密钥、值对
isEmpty（） ：如果大小为零，则返回true

ArrayList<HashNode<K, V>> bucket = new ArrayList<>();

A. 辅助函数 实现的目的是获取密钥的索引，以避免get、add和remove等其他函数中的冗余。该函数使用内置的java函数生成哈希代码，并按HT的大小压缩哈希代码，以便索引在HT的大小范围内

得到（）

get函数只接受一个键作为输入，如果该键存在于表中，则返回相应的值，否则返回null。步骤如下：

检索输入键以在HT中查找索引
如果找到值，则遍历与HT对应的liked列表，如果完全遍历列表而不返回，则返回它，这意味着该值不在表中，无法获取，因此返回null

删除（）

使用helper函数获取与输入键对应的索引
对链表的遍历类似于in get（），但这里的特殊之处在于，在查找键的同时需要删除键，因此出现了两种情况
如果要删除的键位于链接列表的开头
如果要取下的钥匙不在头部而是在其他地方

添加（）

现在我们来看看整个实现中最有趣、最具挑战性的功能。这很有趣，因为当负载因子高于我们指定的值时，我们需要动态增加列表的大小。

就像删除步骤一样，直到遍历和添加，两个案例（在头部点或非头部点添加）保持不变。
接近终点时，如果荷载系数大于0.7
我们将数组列表的大小加倍，然后递归地对现有键调用add函数，因为在我们的例子中，生成的哈希值使用数组的大小来压缩我们使用的内置JVM哈希代码，所以我们需要为现有键获取新的索引。理解这一点非常重要。请重新阅读这一段，直到你了解add函数中发生的事情。

Java确实在自己的哈希表实现中使用了二进制搜索树，如果对应于特定bucket的链表变得太长。

JAVA

                         // Java program to demonstrate implementation of our                       
                         // own hash table with chaining for collision detection                       
                         import                                     java.util.ArrayList;                       
                         import                                     java.util.Objects;                       
           
                         // A node of chains                       
                         class                                     HashNode<K, V> {                       
                                                 K key;                       
                                                 V value;                       
                                                 final                                     int                                     hashCode;                       
           
                                                 // Reference to next node                       
                                                 HashNode<K, V> next;                       
           
                                                 // Constructor                       
                                                 public                                     HashNode(K key, V value,                                     int                                     hashCode)                       
                                                 {                       
                                                 this                                     .key = key;                       
                                                 this                                     .value = value;                       
                                                 this                                     .hashCode = hashCode;                       
                                                 }                       
                         }                       
           
                         // Class to represent entire hash table                       
                         class                                     Map<K, V> {                       
                                                 // bucketArray is used to store array of chains                       
                                                 private                                     ArrayList<HashNode<K, V> > bucketArray;                       
           
                                                 // Current capacity of array list                       
                                                 private                                     int                                     numBuckets;                       
           
                                                 // Current size of array list                       
                                                 private                                     int                                     size;                       
           
                                                 // Constructor (Initializes capacity, size and                       
                                                 // empty chains.                       
                                                 public                                     Map()                       
                                                 {                       
                                                 bucketArray =                                     new                                     ArrayList<>();                       
                                                 numBuckets =                                     10                                     ;                       
                                                 size =                                     0                                     ;                       
           
                                                 // Create empty chains                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < numBuckets; i++)                       
                                                 bucketArray.add(                                     null                                     );                       
                                                 }                       
           
                                                 public                                     int                                     size() {                                     return                                     size; }                       
                                                 public                                     boolean                                     isEmpty() {                                     return                                     size() ==                                     0                                     ; }                       
                                   
                                                 private                                     final                                     int                                     hashCode (K key) {                       
                                                 return                                     Objects.hashCode(key);                       
                                                 }                       
                                   
                                                 // This implements hash function to find index                       
                                                 // for a key                       
                                                 private                                     int                                     getBucketIndex(K key)                       
                                                 {                       
                                                 int                                     hashCode = hashCode(key);                       
                                                 int                                     index = hashCode % numBuckets;                       
                                                 // key.hashCode() could be negative.                       
                                                 index = index <                                     0                                     ? index * -                                     1                                     : index;                       
                                                 return                                     index;                       
                                                 }                       
           
                                                 // Method to remove a given key                       
                                                 public                                     V remove(K key)                       
                                                 {                       
                                                 // Apply hash function to find index for given key                       
                                                 int                                     bucketIndex = getBucketIndex(key);                       
                                                 int                                     hashCode = hashCode(key);                       
                                                 // Get head of chain                       
                                                 HashNode<K, V> head = bucketArray.get(bucketIndex);                       
           
                                                 // Search for key in its chain                       
                                                 HashNode<K, V> prev =                                     null                                     ;                       
                                                 while                                     (head !=                                     null                                     ) {                       
                                                 // If Key found                       
                                                 if                                     (head.key.equals(key) && hashCode == head.hashCode)                       
                                                 break                                     ;                       
           
                                                 // Else keep moving in chain                       
                                                 prev = head;                       
                                                 head = head.next;                       
                                                 }                       
           
                                                 // If key was not there                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 return                                     null                                     ;                       
           
                                                 // Reduce size                       
                                                 size--;                       
           
                                                 // Remove key                       
                                                 if                                     (prev !=                                     null                                     )                       
                                                 prev.next = head.next;                       
                                                 else                       
                                                 bucketArray.set(bucketIndex, head.next);                       
           
                                                 return                                     head.value;                       
                                                 }                       
           
                                                 // Returns value for a key                       
                                                 public                                     V get(K key)                       
                                                 {                       
                                                 // Find head of chain for given key                       
                                                 int                                     bucketIndex = getBucketIndex(key);                       
                                                 int                                     hashCode = hashCode(key);                       
                                   
                                                 HashNode<K, V> head = bucketArray.get(bucketIndex);                       
           
                                                 // Search key in chain                       
                                                 while                                     (head !=                                     null                                     ) {                       
                                                 if                                     (head.key.equals(key) && head.hashCode == hashCode)                       
                                                 return                                     head.value;                       
                                                 head = head.next;                       
                                                 }                       
           
                                                 // If key not found                       
                                                 return                                     null                                     ;                       
                                                 }                       
           
                                                 // Adds a key value pair to hash                       
                                                 public                                     void                                     add(K key, V value)                       
                                                 {                       
                                                 // Find head of chain for given key                       
                                                 int                                     bucketIndex = getBucketIndex(key);                       
                                                 int                                     hashCode = hashCode(key);                       
                                                 HashNode<K, V> head = bucketArray.get(bucketIndex);                       
           
                                                 // Check if key is already present                       
                                                 while                                     (head !=                                     null                                     ) {                       
                                                 if                                     (head.key.equals(key) && head.hashCode == hashCode) {                       
                                                 head.value = value;                       
                                                 return                                     ;                       
                                                 }                       
                                                 head = head.next;                       
                                                 }                       
           
                                                 // Insert key in chain                       
                                                 size++;                       
                                                 head = bucketArray.get(bucketIndex);                       
                                                 HashNode<K, V> newNode                       
                                                 =                                     new                                     HashNode<K, V>(key, value, hashCode);                       
                                                 newNode.next = head;                       
                                                 bucketArray.set(bucketIndex, newNode);                       
           
                                                 // If load factor goes beyond threshold, then                       
                                                 // double hash table size                       
                                                 if                                     ((                                     1.0                                     * size) / numBuckets >=                                     0.7                                     ) {                       
                                                 ArrayList<HashNode<K, V> > temp = bucketArray;                       
                                                 bucketArray =                                     new                                     ArrayList<>();                       
                                                 numBuckets =                                     2                                     * numBuckets;                       
                                                 size =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < numBuckets; i++)                       
                                                 bucketArray.add(                                     null                                     );                       
           
                                                 for                                     (HashNode<K, V> headNode : temp) {                       
                                                 while                                     (headNode !=                                     null                                     ) {                       
                                                 add(headNode.key, headNode.value);                       
                                                 headNode = headNode.next;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method to test Map class                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 Map<String, Integer> map =                                     new                                     Map<>();                       
                                                 map.add(                                     "this"                                     ,                                     1                                     );                       
                                                 map.add(                                     "coder"                                     ,                                     2                                     );                       
                                                 map.add(                                     "this"                                     ,                                     4                                     );                       
                                                 map.add(                                     "hi"                                     ,                                     5                                     );                       
                                                 System.out.println(map.size());                       
                                                 System.out.println(map.remove(                                     "this"                                     ));                       
                                                 System.out.println(map.remove(                                     "this"                                     ));                       
                                                 System.out.println(map.size());                       
                                                 System.out.println(map.isEmpty());                       
                                                 }                       
                         }                       

完整的代码可以在 https://github.com/ishaan007/Data-Structures/blob/master/HashMaps/Map.java

本文由 伊莎安·阿罗拉。 如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

Java