如何将链接列表实现与此哈希函数一起使用以避免冲突

Question

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

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;
        }
    }
}
}

在碰撞

方法的某个地方，它必须根据他的指示进行链表，但我不确定。

Answer 1

参见 LinkedList。

LinkedList允许快速插入和删除。它实现了链接 列表。每个对象都是单独分配的。某些操作不会 需要复制整个集合。在许多常见情况下 链接列表阻碍了性能。

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

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 的行为类似于列表，因为它实现了 ICollection 和 IEnumerable。它比普通的旧数组更方便，因为如果需要，您只需调用 Add 和 Remove 方法即可。