使用语言： 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
- 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"));
}
}
写在最后
#成功的道路没有捷径，唯有不懈的努力，多研究一些底层源码才是王道。