在哈希实现中的线性探测

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

Linear probing in Hashing implementation

问题

以下是翻译好的内容:

static int[] linearProbing(int hash_size, int arr[], int N) {
    int[] a = new int[hash_size];
    for(int i = 0; i < hash_size; i++)
        a[i] = -1;
    for(int i = 0; i < N; i++) {
        int probe = arr[i] % hash_size;
        int offset = 1;
        while(a[probe] != -1) {
            probe = (probe + offset) % hash_size;
        }
        a[probe] = arr[i];
    }
    return a;
}

驱动代码可在以下链接中找到: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:

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {4,14,24,44}

Output:
-1 -1 -1 -1 4 14 24 44 -1 -1

Example 2:

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {9,99,999,9999}

Output:
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 &lt;= hashSize &lt;= 100
1 &lt;= sizeOfArray &lt;= 100
0 &lt;= Array[] &lt;= 105

The code I wrote is:

static int[] linearProbing(int hash_size, int arr[], int N) {
    int[] a = new int[hash_size];
    for(int i = 0; i &lt; hash_size; i++)
        a[i] = -1;
    for(int i = 0; i &lt; N; i++) {
        int probe = arr[i] % hash_size;
        int offset = 1;
        while(a[probe] != -1) {
            probe = (probe + offset) % hash_size;
        }
        a[probe] = arr[i];
    }
    return a;
}

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包含元素的情况下进行迭代。

static int[] linearProbing(int hash_size, int arr[], int N) {
    // 这是您的代码中缺失的部分
    int iterating_size = N > hash_size ? hash_size : N;

    int[] a = new int[hash_size];
    for (int i = 0; i < hash_size; i++)
        a[i] = -1;
    int started = -1;
    for (int i = 0; i < iterating_size; i++) {
        int probe = arr[i] % hash_size;
        int offset = 1;
        while (a[probe] != -1) {
            probe = (probe + offset) % hash_size;
        }
        a[probe] = arr[i];
    }
    return a;
}
英文:

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

static int[] linearProbing(int hash_size, int arr[], int N) {
    //This is what was missing from your code
    int iterating_size = N&gt;hash_size? hash_size : N;

    int[] a = new int[hash_size];
    for(int i = 0; i &lt; hash_size; i++)
        a[i] = -1;
    int started = -1;
    for(int i = 0; i &lt; iterating_size ; i++) {
        int probe = arr[i] % hash_size;
        int offset = 1;
        while(a[probe] != -1) {
            probe = (probe + offset) % hash_size;
        }
        a[probe] = arr[i];
    }
    return a;
}

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:

确定