c# - 将 Hashtable 更改为链表数组

Question

我在我的程序中创建了一个哈希表类。但是我想把它改成一个链表数组。我不熟悉链表，因为它们让我很困惑。谁能解释如何将算法更改为新格式？下面是我创建的哈希表。任何帮助表示赞赏。谢谢！:)

public class hashtable
    {

        //inner class hash entry to be added to hash table
        class hashentry
        {
            int key;
            string data;

            //setters and getters
            public hashentry(int key, string data)
            {
                this.key = key;
                this.data = data;
            }
            public int getkey()
            {
                return key;
            }
            public string getdata()
            {
                return data;
            }
        }


        int maxSize; // table length
        hashentry[] table; //create array of hash entries

        /*
        *
        *Hash table constructor given size paramter to set the length of the array

        *set table to null
        */

        public hashtable(int size)
        {
            maxSize = size;
            table = new hashentry[size];
            for (int i = 0; i < size; i++)
            {
                table[i] = null;
            }
        }

        /*
        * using key, get element at given key parameter, return key to string
        */
        public string retrieve(int key)
        {
            int hash = key % maxSize;
            while (table[hash] != null && table[hash].getkey() != key)
            {
                hash = (hash + 1) % maxSize;
            }
            if (table[hash] == null)
            {
                return "nothing found!";
            }
            else
            {
                return table[hash].getdata();
            }
        }

        /*
        * using string data, get element at given string if it is exact, return hash entry to console
        */
        public void retrievedata(string data)
        {
            for (int i = 1; i <= table.Length; i++)
            {
                try
                {
                    if (table[i].getdata().Equals(data) && table[i].getdata() != null && table != null && i <= maxSize)//if we have null entries
                    {

                        Console.WriteLine("Key value :{0} , Data Value :{1}, Length of Data : {2}", table[i].getkey(), table[i].getdata(), table[i].getdata().Length);
                    }
                    else
                    {
                        continue;
                    }
                }
                catch { }
            }
        }

        /*
        * checks for open spaces in the table for insertion method
        */

        private bool checkOpenSpace()//checks for open spaces in the table for insertion
        {
            bool isOpen = false;
            for (int i = 0; i < maxSize; i++)
            {
                if (table[i] == null)
                {
                    isOpen = true;
                }
            }
            return isOpen;
        }


        /*
        * Method to print all elements of the hash array
        * Print all iterates over all the n elements in the container, so it is o(n) operation.
        */

        public void print()
        {
            for (int i = 0; i < table.Length; i++)
            {
                if (table[i] == null && i <= maxSize)//if we have null entries
                {
                    continue;//dont print them, continue looping
                }
                else
                {
                    Console.WriteLine("Key value :{0} , Data Value :{1}, Length of Data : {2}", table[i].getkey(), table[i].getdata(), table[i].getdata().Length);
                }
            }
        }

        /*
        *Quadratic probe insert is in best case o(1) when location of the hash is empty and in worst
        * case o(n) when it is not empty, so you must loop until you find one that is.
        * if quadratic probe insert is not necessary, it needs to change the pointer to the hash so it is o(1)
        */

        public void quadraticHashInsert(int key, string data)
        {
            // quadratic probing method
            if (!checkOpenSpace())//if no open spaces available
            {
                Console.WriteLine("table is at full capacity!");
                return;
            }

            int j = 0;
            int hash = hash1(key);
            if (hash >= 0)
            {
                while (table[hash] != null && table[hash].getkey() != key && hash >= 0)
                {
                    j++;
                    hash = (hash + j * j) % maxSize;

                    // hash = (hash + j * j) % maxSize;
                }

                if (table[hash] == null)
                {
                    table[hash] = new hashentry(key, data);
                    return;
                }
            }

        }
        private int hash1(int key)
        {
            return key % maxSize;
        }
        private int hash2(int key)
        {
            //must be non-zero, less than array size, ideally odd
            return 5 - key % 5;
        }
    }

标签： c#arrayslinked-listnodeshashtable