如何使用带有此哈希函数的链表实现来避免冲突？

Question

因此，对于我这周 class 的作业，我必须演示一个将数据存储到数据结构中的哈希函数，并使用链表实现来避免冲突。鉴于我教授的源代码，他说代码是正确的，但将数组解决方案更改为链表。我不确定他的意思，但这是下面的代码：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace Hashing
{
class hashFunction
{
    public hashFunction() { }


    public int HashFunc(String s, String[] arr)
    {
        int total = 0;
        char[] cname = s.ToCharArray();
        for (int i = 0; i < cname.Length; i++)
            total += 37 * total + (int)cname[i];
        total = total % arr.Length;
        if (total < 0)
            total += arr.Length;
        return (int)total;
    }

    public int Collision(int oldHashKey, String[] arr)
    {
        int newHashKey = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            newHashKey = 2 * oldHashKey - 1;
            if (arr[newHashKey] == null)
                break;
        }
        return (int)newHashKey;
    }
}


class Program
{
    static void Main(string[] args)
    {
        String[] names = new String[10007];
        String[] Animals = new String[] { "Lions", "Tigers", "Bears", "Aligators", "Snakes", "Eagles" };
        storeMessage(names, Animals);
    }

        public static void storeMessage(String[] arrMessage, String[] arrAnimal)
    {
        hashFunction newHashKey = new hashFunction();
        int[] arrayKeys = new int[arrAnimal.Length];
        String nm; int hashVal;
        for (int i = 0; i < 6; i++)
        {
            nm = arrAnimal[i];
            hashVal = newHashKey.HashFunc(nm, arrMessage);
            while (arrMessage[hashVal] != null)
                hashVal = newHashKey.Collision(hashVal, arrMessage);
            arrMessage[hashVal] = nm;
            arrayKeys[i] = hashVal;
        }
    }
}

}

Collisions 的方法在某个地方，它必须根据他的指示链接列表，但我不确定。

Answer 1

参见LinkedList。

LinkedList allows fast inserts and removes. It implements a linked list. Each object is separately allocated. Certain operations do not require the whole collection to be copied. In many common cases LinkedList hinders performance.

在碰撞中实现这一点的示例：

public int Collision(int oldHashKey, LinkedList<string> arr)
{
    int newHashKey = 0;
    for (int i = 0; i < arr.Count; i++)
    {
        newHashKey = 2 * oldHashKey - 1;
        if (arr[newHashKey] == null)
            break;
    }
    return (int)newHashKey;
}

请注意，实际上并没有太大变化。只是 LinkedList 的行为类似于 List，因为它实现了 ICollection 和 IEnumerable。它比普通的旧数组更方便，因为您可以根据需要调用方法添加和删除。

如何使用带有此哈希函数的链表实现来避免冲突？

How to use a Linked-List implementation with this Hash Function to avoid collisions?

c#

hash

linked-list

collision