HashTable实现原理

使用语言： C#

---

写在前面

好久没写简书，一上来看到那么多朋友的关注和点赞，突然感觉继续写点内容分享一下。
最近正好离职在家，跟网易和腾讯的大牛们，聊了很多底层实现和数据结构的内容，借这个机会写一些，我相信对大家肯定有帮助的。
19年立下大志，把lua底层源码核心内容写在简书中！
19年立下大志，把引擎底层的物理系统整理到简书中！
19年立下大志，把数据结构的应用写到简书中！
个人感觉精通以上三点足矣，进入网易和腾讯都不是问题，说明一下不管你熟不熟悉unity还是ue，对于客户端而言都不是很重要哦。

---

文章内容：

   1. 介绍hashtable的面试问题
   2. 使用Csharp语言实现hashtable

问题：

 1.  hashtable底层实现了解吗？
 2.  hashtable中查找key时，时间复杂度时多少？

解答

  1. hashtable采用的数据结构是散列表，如下图所示，0,1,2,3是索引，指针指向的是对应的key和value值。（不明白？很正常，往下看。）

image.png

2. hashtable查找key的时间复杂度为O(1)-O(n),即最好情况下为O(1)，最差情况下为O（N），查找速度很是很不错的哦。
   这里解释一下，当我们存放key-value为“name”-"mashuai"时， key->name存到hashtable中前，先把字符串“name”转换为hashcode(这是一个整形数值哦）如下，这个hashcode经过数据算法就是hashtable的index索引，也是我们上面散列表的index。
   string key = "name";
   Console.WriteLine (key.GetHashCode()); //62725243
   hashcode = (key.GetHashCode() & int.MaxValue) % table.length

• 注意： string -> hashcode 有好多种算法，自己百度查一下即可。需要注意一点，“name” 和“xxxx”很可能是同一个hashcode。

源码实现(初版。。。很多改进的，主要是put/get思想）

    // HashTable的Node结构
class MyHashEntery<K, V>
{
    public int hash;     // key's hashcode 
    public K key;
    public V value;
    public MyHashEntery<K,V> next;

    public MyHashEntery(int _h, K _k, V _v, MyHashEntery<K,V> _n)
    {
        this.hash = _h;
        this.key = _k;
        this.value = _v;
        this.next = _n;
    }
}

class MyHashTable<K, V>
{
    private MyHashEntery<K,V> [] table;  
    private int count;
    private int threshold;
    private float loadFactor;

    public int Count
    {
        get{return count;}
    }

    public MyHashTable()
    {
        table = new MyHashEntery<K, V>[5];
        count = 0;
        threshold = 10;
    }

    public void Put(K _k, V _v)
    {
        if(_v == null){ throw new Exception("myhashtable's value can't be null!");}

        MyHashEntery<K,V>[] tab = table;

        int hash = _k.GetHashCode();
        int index = (hash & int.MaxValue) % tab.Length;

        MyHashEntery<K,V> temp = tab[index];

        // check key if exist
        while(temp != null)
        {
            if((temp.hash == hash) && temp.key.Equals(_k))
            {
                throw new Exception("key is existed!");
            }
            temp = temp.next;
        }

        if(count >= threshold)
        {
            // expand hashtable  !!temp!!
            threshold = threshold * 2;
            MyHashEntery<K,V>[] newTable = new MyHashEntery<K, V>[table.Length + 5];
            for(int i = 0; i < table.Length; i++)
            {
                newTable[i] = table[i];
            }
            table = newTable;

            tab = table;
            index = (hash & int.MaxValue) % tab.Length;
        }
        MyHashEntery<K,V> e = tab[index];
        tab[index] = new MyHashEntery<K, V>(hash, _k, _v, e);

        count++;
    }

    public V Get(K _k)
    {
        int hash = _k.GetHashCode();
        int index = (hash & int.MaxValue) % table.Length;

        MyHashEntery<K, V> e = table[index];
        while(e != null)
        {
            if(e.hash == hash && e.key.Equals(_k))
            {
                return e.value;
            }
        }

        return default(V);
    }

}
    class MainClass
{
    public static void Main (string[] args)
    {
        MyHashTable<string, string> hash = new MyHashTable<string, string>();
        hash.Put("name1", "35");
        hash.Put("name2", "lua");

        hash.Put("name3", "python");
        
        Console.WriteLine (hash.Get("name1"));
    }
}

写在最后

 #成功的道路没有捷径，唯有不懈的努力，多研究一些底层源码才是王道。