一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1687|回复: 9
收起左侧

[系统设计/OOD] 求问一道设计题,设计多线程的hashmap

[复制链接] |试试Instant~ |关注本帖
silenceleaf 发表于 2015-12-2 17:15:47 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
小弟求问一道设计题,要求设计多线程的hashmap。我第一个想到的是整个map就一个lock,然后每次读写锁住就好了。但是这样并没有真正的多线程操作,所以要给每个slot加一个lock。那问题来了,就算每个slot一个锁,那在算hash function的时候是不是也要加锁?还有没有别的地方也要加锁?感觉问题变得非常复杂无从下手。请问哪位大大能帮忙解答一下呢?非常感谢!
sanguine 发表于 2015-12-3 00:36:51 | 显示全部楼层
去看看ConcurrentHashMap源码?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| silenceleaf 发表于 2015-12-3 01:54:10 | 显示全部楼层
sanguine 发表于 2015-12-3 00:36
去看看ConcurrentHashMap源码?

我看了一下,但是好像是整个map用一个锁,并不符合要求
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-12-3 05:09:45 | 显示全部楼层
silenceleaf 发表于 2015-12-2 12:54
我看了一下,但是好像是整个map用一个锁,并不符合要求

不是吧,那个是HashTable的实现吧?所以才inefficiency
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-5 19:36:51 | 显示全部楼层
纯探讨哈。我觉得关键原则是保证没有两个线程同时操作同一块内存区域,所以如果不对整个map加锁,那么至少对每个slot加一个锁应该是必要的。还有个要注意的地方是map的长度可能会不停地扩展,扩展后可能需要移动之前放在内存区域里的内容;这个过程进行的时候应该不能有任何其他进程对内存的读写。所以这个地方需要对整个map加锁。hash function可能需要用到map的长度,所以在map的长度扩展时同时也要锁住所有hash function的计算,等长度扩展完成后再恢复。

多线程这块我其实没有学过,纯粹是个人脑补,望指正。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| silenceleaf 发表于 2015-12-6 03:11:29 | 显示全部楼层
stellari 发表于 2015-12-5 19:36
纯探讨哈。我觉得关键原则是保证没有两个线程同时操作同一块内存区域,所以如果不对整个map加锁,那么至少 ...

完全和我和同学讨论的结果一样!哈哈哥们牛b啊!
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-12-6 03:27:29 | 显示全部楼层
参考下这个?
http://www.iteye.com/topic/344876
回复 支持 反对

使用道具 举报

Seattlexxx 发表于 2015-12-7 14:05:32 | 显示全部楼层
用 CopyOnWriteHashMap。具体得查查
回复 支持 反对

使用道具 举报

Seattlexxx 发表于 2015-12-7 14:11:28 | 显示全部楼层
回复 支持 反对

使用道具 举报

hooloovoo 发表于 2015-12-11 02:08:12 | 显示全部楼层
There are two approaches: blocking vs non-blocking. Blocking is about using locks, either course-grain lock or fine-grained lock (lock to each bucket). Lock-free hashmap is based on compare-and-swap (CAS). The main difficulty is concurrent resizing.
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 13:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表