多线程的map的处理

我开发的时候遇到一个难题。

需求是这样的：

有一个map的数据结构，用于保存某些值。
类似：map<int, Struct*> data;


有N个线程在访问它，读取其中的Struct*指针。
读取大概如：Struct * ptr = data[key];

还有一个线程是会修改它，或者新增值。
新增大概如： Struct * newValue = new Struct(); data[newKey] = newValue;
修改大概如：Struct * value = data[key]; value->val1 = 145; value->val2=232; value->val3=35432;

如果不考虑效率的话，用读写锁是最简单的了。但是问题在于我的读线程可能每秒访问数万次，使用读写锁明显造成性能瓶颈啊。


请问有没有别的什么方案。不限于map。
1、可以高效的通过key查询到value。
2、可以不加锁的插入。
3、可以不加锁的修改（此时读取到脏数据无所谓，只要系统不崩溃即可）。

在正确性与性能之间，我选择正确性