我的强迫症就这时候容易犯 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

我的强迫症就这时候容易犯

我的强迫症就这时候容易犯# Joke - 肚皮舞运动

a*82012-10-12 07:10

1 楼

一个小时的phone interview
让实现一个支持多线程的hashmap （就是支持分布式系统的）
完全没有想法挂了
给大家讨论一下

c*72012-10-12 07:10

2 楼

坐地铁，身边一个男孩提醒我：“你鞋带开了。”由于车厢很挤，鞋带也不长，我就说
：“我一会儿就系上。”车开了两站，期间男孩一直时不时侧头看我。到了第三站，男
孩终于忍不住对我说：“你能系上么？看着好难受啊……”

j*y2012-10-12 07:10

3 楼

bless.
感觉就是对于 insert, find, delete 这些操作需要 lock吧？

【在 a*****8 的大作中提到】

: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法挂了
: 给大家讨论一下

M*52012-10-12 07:10

4 楼

这道题就是考你在实现push和pop的时候要用个thread_lock吧，应该，好像不需要很多多
线程的概念。。。不知道还有没有人有其他意见。。。

h*n2012-10-12 07:10

5 楼

其实就是对query，insert，delete操作加锁即可
注意不要对整个hashtable加锁，这样子并行化性能低下
要对每一次被indexed的slot加锁

【在 a*****8 的大作中提到】

: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法挂了
: 给大家讨论一下

w*x2012-10-12 07:10

6 楼

该不是要实现lock free的hash map吧

c*a2012-10-12 07:10

7 楼

是不是类似这样，不太懂系统
private Lock lock = new Lock();
public int delete(int x){
lock.lock();
int val = super.delete(x);
lock.unlock();
return val;
}
The lock() method locks the Lock instance so that all threads calling lock()
are blocked until unlock() is executed.

M*52012-10-12 07:10

8 楼

这个怎么实现，加thread_lock的时候不就是
void insert(int num){
thread_lock();
map.insert(num);
thread_unlock();
}
没有注意语法的正确与否，只表达了idea。。。加锁的时候不是整个container的数据
都lock起来了吗？

【在 h****n 的大作中提到】

: 其实就是对query，insert，delete操作加锁即可
: 注意不要对整个hashtable加锁，这样子并行化性能低下
: 要对每一次被indexed的slot加锁

j*y2012-10-12 07:10

9 楼

对 slot 加锁怎么做阿？我下面的code 感觉是对整个 hash table加锁了。
请指点，多谢 :)
class hashmap
{
int m;
pair table[m];
pthread_mutex_t lock;
int hashfunc(string);
public:
void insert(pair v)
{
pthread_mutex_lock(&lock);
int slot = hashfunc(v.first);
table[slot] = v;
pthread_mutex_unlock(&lock);
}

};

【在 h****n 的大作中提到】

: 其实就是对query，insert，delete操作加锁即可
: 注意不要对整个hashtable加锁，这样子并行化性能低下
: 要对每一次被indexed的slot加锁

h*n2012-10-12 07:10

10 楼

题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
hashtable slot数目一致，一一对应
如果对并行性能要求不高那就另当别论了

【在 j*****y 的大作中提到】

: 对 slot 加锁怎么做阿？我下面的code 感觉是对整个 hash table加锁了。
: 请指点，多谢 :)
: class hashmap
: {
: int m;
: pair table[m];
: pthread_mutex_t lock;
: int hashfunc(string);
: public:
: void insert(pair v)

j*y2012-10-12 07:10

11 楼

明白意思了, 需要一对一的 mutex来锁定相应的 slot. 如果只有一个 mutex 的话，
就只能锁定整个 table了吧？多谢 :)

【在 h****n 的大作中提到】

: 题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
: 如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
: hashtable slot数目一致，一一对应
: 如果对并行性能要求不高那就另当别论了

M*52012-10-12 07:10

12 楼

多谢指点，明白了。。。

【在 h****n 的大作中提到】

j*y2012-10-12 07:10

13 楼

还有一个问题，　对于 queue 里面的操作，　能做到对于 slot 来锁定吗？　感觉
要复杂些，　因为 dequeue 和 enqueue 有依赖关系.

【在 h****n 的大作中提到】

h*n2012-10-12 07:10

14 楼

queue和这个问题不太一样，hash里面的slot是independent所以才能这么做，queue要
对整个queue加锁的，所能优化的地方有两点，第一个是尽量降低临界区也就是锁的时
间，第二个就是要采用semaphore同步机制来避免queue为空的时候pop操作busy loop，
queue满的时候push操作busy loop。具体可参考semaphore如何解决经典的生产者消费
者问题

【在 j*****y 的大作中提到】

: 还有一个问题，　对于 queue 里面的操作，　能做到对于 slot 来锁定吗？　感觉
: 要复杂些，　因为 dequeue 和 enqueue 有依赖关系.

y*g2012-10-12 07:10

15 楼

多线程hashmap 和支持分布式系统的DHT区别很大吧？
多线程concurrenthashmap就可以了。主要idea就是分bucket来lock

【在 a*****8 的大作中提到】

: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法挂了
: 给大家讨论一下

h*n2012-10-12 07:10

16 楼

agree，这两个问题是有区别，分布式的话hash table要分配到各个机器上，而不是整
个存在一个机器里面，之间需要协议来保证coherency 不过感觉电面的话分布式应该不
会让你设计，这可不是十几二十分钟能搞定的，顶多说说idea

【在 y*******g 的大作中提到】

: 多线程hashmap 和支持分布式系统的DHT区别很大吧？
: 多线程concurrenthashmap就可以了。主要idea就是分bucket来lock

c*t2012-10-12 07:10

17 楼

难道不是简单的synchronized就行吗？如下：
public class NewHashMap extends HashMap {
public synchronized void put(K a, V b){
super.put(a,b);
}

public synchronized V get(K a){
return super.get(a);
}
}

【在 a*****8 的大作中提到】

: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法挂了
: 给大家讨论一下

c*t2012-10-12 07:10

18 楼

哦，我也后知后觉了。多谢！

【在 h****n 的大作中提到】

j*y2012-10-12 07:10

19 楼

谢谢。　刚才看了那个 consumer/producer 的 wiki, 对于 queue而已就是要对于
queue的size用 semaphore, 是吧?

【在 h****n 的大作中提到】

: queue和这个问题不太一样，hash里面的slot是independent所以才能这么做，queue要
: 对整个queue加锁的，所能优化的地方有两点，第一个是尽量降低临界区也就是锁的时
: 间，第二个就是要采用semaphore同步机制来避免queue为空的时候pop操作busy loop，
: queue满的时候push操作busy loop。具体可参考semaphore如何解决经典的生产者消费
: 者问题

h*n2012-10-12 07:10

20 楼

其实两个binary semaphore就足够了，一个sem_full另外一个是sem_empty 初值都为0
pop操作只有在检测到queue为空的时候才去wait(sem_full)，当push一个新元素的时候
都会去notify一个等待的线程
push操作检测queue为满的时候做类似操作
如果光用mutex的话，当queue为空的话，做pop操作的线程即使拿到mutex每次都检测到
queue为空，这样子就做了很多无谓的工作，还占用了时间片
而用同步机制的话，这种情况下会被scheduler直接放进pending list里面直到被
notify避免了cpu的浪费

【在 j*****y 的大作中提到】

: 谢谢。　刚才看了那个 consumer/producer 的 wiki, 对于 queue而已就是要对于
: queue的size用 semaphore, 是吧?