寡人写代码的那些事，分享一下

wlmqgzm

windoze 发表于 2016-12-29 00:17
open addressing最大的问题是必须预留两个元素，一个表示未占用，另一个表示已删除。
cache友好就不要想了 ...

对的，常规的　open addressin　有　两个元素，一个表示未占用，另一个表示已删除，所以，觉得不够优化。
修改为　unsigned int  uint_distance;　其中拿出一个bit表示　未占用或者已经删除，　其余bit表示最大搜索长度，这样在数据比较满的情况下有更好的性能。
步进长度为１，所以cache友好

template<typename KEY, typename VALUE>
class  Struct_circular_hash_map_record
{
   public:
     Struct_circular_hash_map_record( void );

     #ifdef  CIRCULAR_HASH_MAP_HAS_MEMORY_COUNT
     size_t  capacity( void );
     #endif // CIRCULAR_HASH_MAP_HAS_MEMORY_COUNT

     #ifdef   CIRCULAR_HASH_MAP_VALUE_HAS_VERSION
     void     init_version( void );
     void     increase_version( void );
     unsigned int  uint_version;
     #endif // CIRCULAR_HASH_MAP_VALUE_HAS_VERSION

     unsigned int  uint_distance;
     unsigned int  uint_hash;
     KEY  key;
     VALUE  value;
};

lxyscls

wlmqgzm 发表于 2016-12-29 20:55
对的，常规的　open addressin　有　两个元素，一个表示未占用，另一个表示已删除，所以，觉得不够优化。 ...

线性探查

没有实际写过，只能搬一下《算法导论》里面的描述：容易出现群集现象

Python内部的dict结构，也是开发寻址，但不是线性探查

wlmqgzm

lxyscls 发表于 2016-12-30 09:53
线性探查

没有实际写过，只能搬一下《算法导论》里面的描述：容易出现群集现象

主要是hash计算出的数据是否足够　平均分布，　而不是挤在一起，我觉得基于intel SSE4.2指令集的 crc32c的算法，算比较优秀，　即使是８５％以上的容量占用，性能也还是很好。

sditmaner

因为是自主的，所以是可发展的

action08

lxyscls 发表于 2016-12-30 09:53
线性探查

没有实际写过，只能搬一下《算法导论》里面的描述：容易出现群集现象

看来大家都应该考虑使用高级语言，好多高科技在里面