HashMap实现
一直不懂HashMap的实现,直到看到了一篇博客,才恍然大悟。先简单写几笔,之后再更新。
HashMap的实现是数组加链表。HashMap的主体是个数组,
private Element<TK, TV>[] _objects = { };
数组的查找时间复杂度O(1),数组里的元素类似这种结构。
class Element<TK, TV>
{
public TK K;
public TV V;
public long HashValue; // key的HashValue
public Element<TK, TV>? Next; // 下一个节点
}
Next是下一个节点,主体数组下标是k的hash值,HashMap添加的时候,k的hash值处已存在元素,也就是两个元素的hash值相同,那么就加到相同hash值节点的下一个节点上,从而形成个链表。
向HashMap添加元素。( 注:只是演示个大概意思,代码可能不能运行)
public void Put(TK k, TV v)
{
var hashCode = k.GetHashCode();// 得到hash值
var element = new Element<TK, TV>();
element.HashValue = hashCode;
if (_objects.Contains<>(hashCode)) // 已经存在元素,那么就加在后一个节点
{
var next = _objects[hashCode];
while (next != null)
{
next = next.Next;
}
if (next != null) next.Next = element;
return;
}
_objects[hashCode] = element;
}
从HashMap得到一个元素,如果数组中存在那个元素的hash值,那么判断那个元素是否是个链表,也就是hash值相同的一堆元素。如果是个链表,那么就判断k是否相同。添加的时候数组下标是k的hash值,可能两个k的hash值相同。(
注:只是演示个大概意思,代码可能不能运行)
public TV Get(TK k)
{
var hashCode = k.GetHashCode();
var element = _objects[hashCode];
while (element.Next != null && element.HashValue != hashCode && element.K != k)
{
element = element.Next;
}
return element.V;
}
一个HashMap的好坏主要看Hash函数,如果Hash函数得出来的值都相同,那不就和链表一样了。。。
未完待续~~~