C#哈希表

1.概要

散列表(Hash table哈希表),是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,可以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。.

C#哈希表

下面来看一个案例,是google的一个面试题:

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,名字,年龄,住址)当输入该员工id时,要求查找到该员工的所有信息。

要求:

不适用数据库,速度越快越好。哈希表添加时,保证按照id从低到高插入。

思路:

(1)使用链表来实现哈希表,该链表不带表头(即:链表的第一个节点就是存放雇员信息)。

(2)思路分析并画出示意图

(3)代码实现增删改查

C#哈希表

2.详细内容

   /// <summary>
   /// 表示一个雇员
   /// </summary>
   public class Emp
  {
       public int Id { get; set; }
       public string Name { get; set; }
       public int Age { get; set; }
       /// <summary>
       /// 默认为null
       /// </summary>
       public Emp Next { get; set; }
       public Emp(int id, string name, int age)
      {
           Id = id;
           Name = name;
           Age = age;
      }
  }

   /// <summary>
   /// 创建EmpLinkedList链表
   /// </summary>
   public class EmpLinkedList
  {
       /// <summary>
       /// 头指针,执行第一个Emp,因此我们这个链表的head时直接只想第一个emp
       /// </summary>
       public Emp Head { get; set; }
       public EmpLinkedList()
      {
           Head = null;
      }

       /// <summary>
       /// 添加雇员到链表
       /// 1.假定当添加雇员时id时自增长的,即id的分配总是从小到大。因此我们将该雇员直接加入到本地链表的最后即可
       /// </summary>
       /// <param name="emp"></param>
       public void Add(Emp emp)
      {
           if (Head == null)
          {
               Head = emp;
          }
           else
          {
               //如果不是第一个雇员,则使用一个辅助的指针,帮助定位到最后
               Emp temp = Head;
               while (temp.Next != null)
              {
                   temp = temp.Next;
              }
               temp.Next = emp;
          }
      }

       /// <summary>
       /// 根据id查找雇员
       /// 如果查找到就返回,没有返回null
       /// </summary>
       /// <param name="id"></param>
       /// <returns></returns>
       public Emp FindEmpById(int id)
      {
           //判断链表当前是否为空
           if (Head == null)
          {
               Console.WriteLine("链表为空!");
               return null;
          }
           Emp currentEmp = Head;
           while (true)
          {
               if (currentEmp.Id == id)
              {
                   //设置时候currentemp就指向要查找到的雇员
                   break;
              }

               //退出
               if (currentEmp.Next == null)
              {
                   //说明便利当前链表没有查找到该雇员
                   currentEmp = null;
                   break;
              }
               currentEmp = currentEmp.Next;
          }
           return currentEmp;
      }

       /// <summary>
       /// 打印
       /// </summary>
       public void Print()
      {
           Emp temp = Head;
           while (temp != null)
          {
               Console.WriteLine(temp.Id + " " + temp.Name + " " + temp.Age);
               temp = temp.Next;
          }
      }
  }

   public class HashTable
  {
       private EmpLinkedList[] arr;
       private int _size;

       public HashTable(int size)
      {
           arr = new EmpLinkedList[size];
           _size = size;
           //分别初始化每个链表
           for (int i = 0; i < size; i++)
          {
               arr[i] = new EmpLinkedList();
          }
      }

       /// <summary>
       /// 添加雇员
       /// </summary>
       /// <param name="emp"></param>
       public void Add(Emp emp)
      {
           //根据员工的id,得到该员工的哈希值
           int hashCode = GetHashCode(emp.Id);
           //将emp添加到对应的链表中
           arr[hashCode].Add(emp);
      }

       public void FindEmpById(int id)
      {
           //使用散列函数确定到那条链表查找
           int hashcode = GetHashCode(id);
           Emp emp = arr[hashcode].FindEmpById(id);
           if (emp != null)
          {
               //找到了
               Console.WriteLine($"在第{hashcode + 1}条链表中找到雇员id = { id }");
          }
           else
          {
               Console.WriteLine("在哈希表中,没有找到该雇员~");
          }
      }

       //遍历所有的链表,打印所有的雇员
       public void Print()
      {
           for (int i = 0; i < _size; i++)
          {
               arr[i].Print();
          }
      }

       //编写一个散列函数,使用一个简单的取模法
       public int GetHashCode(int id)
      {
           return id % arr.Length;
      }
  }
       static void Main(string[] args)
      {
           HashTable hashTable = new HashTable(7);
           hashTable.Add(new Emp(2345, "emp" + 678, 15));
           hashTable.Add(new Emp(1, "emp" + 678, 15));
           hashTable.Add(new Emp(2, "emp" + 678, 15));
           hashTable.Add(new Emp(123, "emp" + 678, 15));
           hashTable.Print();
           hashTable.FindEmpById(123);
           Console.Read();
      }

C#哈希表

C#哈希表