7
回答
哈,喷下时间戳和链扫描
科大讯飞通用文字识别100000次/天免费使用。立即申请   

@乌龟壳 关于链的扫描,在我自己做的库中,大体的算法如下:(假设链的节点不会超过 2的32次方。 则每个节点存在一个32位正整数的时间戳成员)

1、每次扫描,总会先额外做个工作,按存储空间顺序,更新一个节点的时间戳。这样,总能能在2的32次方次扫描前,所有存储节点的时间戳被更新,也即,任意节点的时间戳所记录的数值与当前的计次数值的距离不会大于2的32次方

2、每扫描一个节点前,更新扫描计数(累加)

3、判断该节点的时间戳的计数是否与本次扫描计数相等,如果相等则表示访问过。

4、每次访问过的节点,将本次扫描计数的值写入时间戳的成员数据中。

这样做,会费些存储,相对bit map的方式,不过每次扫描前额外的计算工作会很少。所以没啥特定应用环境时,我都是这么玩。哈。

<无标签>
举报
中山野鬼
发帖于1年前 7回/598阅
顶部