在哈希实现中的线性探测

huangapple go评论109阅读模式
英文:

Linear probing in Hashing implementation

问题

以下是翻译好的内容:

  1. static int[] linearProbing(int hash_size, int arr[], int N) {
  2. int[] a = new int[hash_size];
  3. for(int i = 0; i < hash_size; i++)
  4. a[i] = -1;
  5. for(int i = 0; i < N; i++) {
  6. int probe = arr[i] % hash_size;
  7. int offset = 1;
  8. while(a[probe] != -1) {
  9. probe = (probe + offset) % hash_size;
  10. }
  11. a[probe] = arr[i];
  12. }
  13. return a;
  14. }

驱动代码可在以下链接中找到:https://i.stack.imgur.com/ULVdd.png

英文:

I am trying to solve this problem where I need to implement Linear Probing.

Given an array of integers and a hash table size. Fill the array elements into a hash table using Linear Probing to handle collisions.

Example 1:

  1. Input:
  2. hashSize = 10
  3. sizeOfArray = 4
  4. Array[] = {4,14,24,44}
  5. Output:
  6. -1 -1 -1 -1 4 14 24 44 -1 -1

Example 2:

  1. Input:
  2. hashSize = 10
  3. sizeOfArray = 4
  4. Array[] = {9,99,999,9999}
  5. Output:
  6. 99 999 9999 -1 -1 -1 -1 -1 -1 9

Your Task:<br/>
You don't need to read input or print anything.

Your task is to complete the function linearProbing() which takes as input a empty hash table (hash), the hash table size (hashSize), an integers array arr[] and its size N and inserts all the elements of the array arr[] into the given hash table.

The empty cells of the hash table are to be given a value of -1. Also, if there's no more space to insert a new element, just drop that element.

Expected Time Complexity: O(N). <br>
Expected Auxiliary Space: O(1).

Constraints:

  1. 1 &lt;= hashSize &lt;= 100
  2. 1 &lt;= sizeOfArray &lt;= 100
  3. 0 &lt;= Array[] &lt;= 105

The code I wrote is:

  1. static int[] linearProbing(int hash_size, int arr[], int N) {
  2. int[] a = new int[hash_size];
  3. for(int i = 0; i &lt; hash_size; i++)
  4. a[i] = -1;
  5. for(int i = 0; i &lt; N; i++) {
  6. int probe = arr[i] % hash_size;
  7. int offset = 1;
  8. while(a[probe] != -1) {
  9. probe = (probe + offset) % hash_size;
  10. }
  11. a[probe] = arr[i];
  12. }
  13. return a;
  14. }

The given testcases are running. But when submitting I am getting TLE. Please help.

The driver code is given as follows =
https://i.stack.imgur.com/ULVdd.png

答案1

得分: 1

你漏掉了一个关键点,当数组大小大于哈希表时,只需跳过剩余部分。

这也可能是一个简单的要点,只需用哈希表大小替换N并进行迭代。这将使您只需在arr包含元素的情况下进行迭代。

  1. static int[] linearProbing(int hash_size, int arr[], int N) {
  2. // 这是您的代码中缺失的部分
  3. int iterating_size = N > hash_size ? hash_size : N;
  4. int[] a = new int[hash_size];
  5. for (int i = 0; i < hash_size; i++)
  6. a[i] = -1;
  7. int started = -1;
  8. for (int i = 0; i < iterating_size; i++) {
  9. int probe = arr[i] % hash_size;
  10. int offset = 1;
  11. while (a[probe] != -1) {
  12. probe = (probe + offset) % hash_size;
  13. }
  14. a[probe] = arr[i];
  15. }
  16. return a;
  17. }
英文:

You missed out one single point, when the array size is bigger than the hash table, just skip the rest.

This could also be the simple point, Just replace N with hash_size and iterate. This would let you only iterate as long as arr contains elements

  1. static int[] linearProbing(int hash_size, int arr[], int N) {
  2. //This is what was missing from your code
  3. int iterating_size = N&gt;hash_size? hash_size : N;
  4. int[] a = new int[hash_size];
  5. for(int i = 0; i &lt; hash_size; i++)
  6. a[i] = -1;
  7. int started = -1;
  8. for(int i = 0; i &lt; iterating_size ; i++) {
  9. int probe = arr[i] % hash_size;
  10. int offset = 1;
  11. while(a[probe] != -1) {
  12. probe = (probe + offset) % hash_size;
  13. }
  14. a[probe] = arr[i];
  15. }
  16. return a;
  17. }

huangapple
  • 本文由 发表于 2020年10月14日 12:53:54
  • 转载请务必保留本文链接:https://go.coder-hub.com/64346811.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定