百度终面结构设计题（实现HashMap）

根据自己的想法实现HashMap

我的思路:

1. 设置一个长度为26的数组,数组每个元素都指向一个单链表(现在认为,如果26改成26*2+10可能会更合理)

2. 哈希函数的选择:根据关键字的第一个字符,通过计算(mod 26的操作返回的值),找到数组对应的存储数据单链表

3. 单链表存储的数据的结构

typedef struct item
{
	char* key;
	char* value;
	struct item *next;
}node;

 

 

4. 主要操作

put操作: 根据key找到对应的单链表,遍历该单链表,其中数据的key字段值与当前key相同,则更新该数据的value字段值.

get操作: 根据key找到对应的单链表,遍历该单链表,其中数据的key字段值与当前key相同,则找到,返回value字段值.

 

没想到我的想法是对的~~

 

以下摘自: http://zhangshixi.javaeye.com/blog/672697

HashMap的数据结构：
   在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。



从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

 

评论

3 楼 yeshaoting 2011-12-01  

zuoyetian 写道

当时没问到碰撞吗？

才看到有评论.你说的碰撞是同义词发生冲突的情况怎么解决吗?

2 楼 zuoyetian 2011-11-10  

当时没问到碰撞吗？

1 楼 zuoyetian 2011-11-10  

very nice！