数据结构HashTable，C#语言实现

SeqList类：

using System;
using System.Text;

namespace hashtable.List {
    public class SeqList<T>  {
        private T[] element;
        //顺序表的数组容量
        private int size;
        //顺序表的长度
        private int length;

        public SeqList(int size) {
            this.size = size < 64?64:size;
            this.element = new T[this.size];
            this.length = 0;
        }

        public SeqList(T[] value){
            int n = value.Length;
            if(n>0) {
                this.size = 2*n;
                this.element = new T[this.size];
                for(int i=0;i<n;i++){
                    this.element[i] = value[i];
                }
                this.length = n;
            }
        }

        public bool isEmpty() {
            return this.length == 0;
        }

        public T get(int i) {
            if(i>=0 && i<this.length) {
                return this.element[i];
            }
            throw new Exception("指定的参数索引无效!!");
        } 

        public bool set(int i, T x) {
            if(i>=0 && i<this.length) {
                this.element[i] = x;
                return true;
            }
            return false;
        }

        public void insert(int i, T x) {
            if(this.length == this.size) {
                T[] temp = element;
                element = new T[size * 2];
                this.size = this.size * 2;
                for(int j=0;j<size;j++){
                    this.element[j] = temp[j];
                } 
            }

            if(i<0) i=0;
            if(i>length) i = length;
            for(int j=length-1;j>=i;j--){
                element[j+1] = element[j];
            }
            element[i] = x;
            length ++;
        }

        public void insert(T x) {
            this.insert(length,x);
        }


        public bool remove(int i, ref T old) {
            if(length > 0 && i>=0 && i<length) {
                old = element[i];
                for(int j=i;j<length;j++) {
                    element[j] = element[j+1];
                }
                length --;
                return true;
            }

            return false;
        }


          public bool remove(T old) {
            int i = this.index(old);
            if(i<0) {
                return false;
            }
            this.remove(i,ref old);
            return true;
        }


        public int index(T value) {
            for(int i=0;i<this.length;i++){
                if(this.element[i].Equals(value)) {
                    return i;
                }
            }

            return -1;
        }

        public  override string ToString() {
            StringBuilder sb = new StringBuilder();
            sb.Append("(");
            
            if(this.length == 0) {
                sb.Append(")\n");
                return sb.ToString();
            }

            sb.Append(this.get(0));
            for(int i=1;i<this.length;i++){
                sb.Append(", "+this.get(i));
            }
            sb.Append(")\n");
            return sb.ToString();
        }

        public bool contains(T value){
            return index(value) >= 0;
        }
        public void clear() {
            this.length = 0;
        }
    }
}

HashTable类：

using hashtable.List;
using System;
using System.Text;

namespace hashtable.Hash {
    public class HashTable {
        private SeqList<int> []  table;
        private int size;
        public HashTable(int size) {
            this.size = size;
            this.table = new SeqList<int>[size];

            for(int i=0;i<table.Length;i++){
                 table[i] = new SeqList<int>(64);
            }
        }

        public int hash(int key) {
            return key % size;
        }

        public void insert(int key) {
            int i = hash(key);
            table[i].insert(key);
        }

        public bool remove(int key) {
            return table[hash(key)].remove(key);
        }

        public int search(int key) {
            return table[hash(key)].index(key);
        }

        public bool contains(int key) {
            return search(key) != -1;
        }

        public override string ToString(){
            StringBuilder sb = new StringBuilder();
            sb.Append("哈希表：\n");
            for(int i=0;i<table.Length;i++){
                sb.Append($"table {i}: {table[i]}");
            }
            sb.Append("\n");
            return sb.ToString();
        }


    }
}

主程序类:

using System;
using hashtable.Hash;

namespace hashtable
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 10;
            int[] keys = {9, 4, 12, 3, 1, 14, 74, 6, 16, 96};
            HashTable ht = new HashTable(N);
            for(int i=0;i<N;i++){
                ht.insert(keys[i]);
            }

            Console.Write(ht);

        }
    }
}

程序输出：

1.png