假设在一个固定的时间间隔内，有数百万的客户端在向一台服务器发送心跳，那么服务器判断客户端停止发送心跳的时间大于时间间隔失败。如果服务器只维护一个映射并不断迭代每个客户端以检查客户端是否超时，那将产生 O(n) 的复杂性，这对数百万客户端来说是可怕的。是否有一些算法可以像一些堆或二叉树一样使 O(log(n)) 复杂度来解决这样的问题？谢谢。
最佳答案
如果你保留一个双链表和一个散列图，你可以使用散列图找到与发送心跳的客户端对应的列表条目。 收到心跳后，您将列表条目解链并将其放在链表的末尾。
链表开头的条目是一个候选的“死亡”客户端。 链表可以遍历到第一个存活的客户端。
一些注意事项:
添加客户: 创建一个列表条目，将其添加到 HashMap 和链表的末尾。 O(1)
移除一个客户端: 通过在 HashMap 中查找来找到客户端列表条目。解开客户端。从 HashMap 中删除。 O(1).
处理心跳: 通过在 HashMap 中查找来找到客户端列表条目。取消链接客户端列表条目。将列表条目添加到链接列表的末尾。 O(1)
找到一个死去的客户: 查看链接列表的第一个条目。 O(1)
关于algorithm - 是否有任何好的算法来检测停止向服务器发送心跳的客户端？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30454209/