如果无法定义此类型的哈希表，则无锁

block is there are =1 task could progress if there are N tasks concurrent running 
and one enter the critical area(enter the critical area one).
lock-free is there are >=1 tasks could progress if there are N tasks concurrent 
running and one enter the critical area.
wait-free is there are N tasks could progress if there are N tasks concurrent 
running and one enter the critical area(maybe it shouldn't be called `critical area`).

bucket
+-------------+      +-------+      +-------+
| head | lock | ---> | entry | ---> | entry | ---> ...
+-------------+      +-------+      +-------+

如果一个哈希表有N个bucket，并且每个bucket都有一个锁，那么在任何时候，都应该有>=1个任务在进行中。这种类型的哈希表是否可以定义为无锁？

没有。"每一个都有一个锁"意味着潜在的阻塞。作为"无锁"的测试，请考虑一个挂起的线程是否会阻止另一个线程在其挂起的整个时间内取得进展。如果是这样，那么这就不是一个无锁的情况。

在无锁编程中，你使用类似原子操作的东西——通常会出现旋转更新失败——这样，试图取得进展的线程可能必须重试，但每次都有新的竞争条件来查看它们是否取得进展；他们有一个真正的机会。

旋转锁定

（我在评论中提供了一些细节，但这变得很笨拙。）

"旋转锁"对不同的人来说意味着不同的东西。

从历史上看，如果互斥锁或读写锁在加入该锁的操作系统队列之前尝试原子获取该锁至少要跨越几次（十万/千次），一些人就会将其称为旋转锁（因此，如果持有该锁的线程长时间运行，它就不会持续烧录CPU）。

Microsoft位于http://msdn.microsoft.com/en-us/library/ms894034.aspx以不同的方式使用：

只有持有旋转锁的线程才能使用资源，并且只能在释放锁之前使用。旋转锁阻止其他线程访问资源。在等待旋转锁释放时，另一个线程可以启动一个循环，尝试获取旋转锁并继续循环，直到持有该锁的线程释放旋转锁为止。

因此，在这种情况下，他们认为旋转锁类似于我上面描述的用法，但没有提供回退到事件驱动的队列以避免占用CPU时间。

无锁原子操作往往也在旋转——不同的是，它们在旋转停止时已经完成了工作，而不是关闭竞争线程以允许它们开始工作（并且即使锁定线程以某种方式被挂起或延迟，也会阻止这些竞争线程进行）。

我对免锁的理解是：

有多个任务正在并发运行，每个任务都可以访问共享数据，而不会有任何任务阻碍其他任务的进度。因此，如果您挂起一个线程，它将永远不会阻止其他线程取得进展。

所以（我认为）如果你使用任何锁，你的代码都不是无锁的。实际上，您使用锁正是因为多个线程可能会尝试并发访问共享数据，因此此单个锁可能会受到质疑并串行访问；很明显，这种可能性意味着您的代码不是无锁的。您在存储桶中使用的锁可能是mutex（操作系统管理队列并在获取锁时提供事件通知）或繁忙循环（CPU在应用程序空间中旋转，试图以原子方式独占获取锁），但两者都不是无锁的。

如果满足以下条件，则对back-off使用某些技术是无锁的：Also if you suspend a single thread, it will never prevent other threads from making progress.。

在您的哈希表中，多个线程可以取得进展，但尽管如此，当对同一bucket中的元素进行操作时，线程可以相互阻塞。在bucket的链表中，您可以使用细粒度的锁——让多个线程处理列表中的元素——但即使这样也不是真正的无锁。

编辑

无锁定和无等待之间的区别（C++ Concurrency in action书中的定义）：

无锁：要使数据结构符合无锁条件，必须有多个线程能够同时访问数据结构。他们不一定能做同样的事情运营；无锁队列可能允许一个线程推送一个线程弹出，但是如果两个线程试图同时推送新项目，则中断。不仅如此，如果访问数据结构的线程在中途被调度程序挂起通过它的操作，其他线程必须仍然能够在不等待挂起的线程的情况下完成它们的操作。

经常对数据结构使用比较/交换操作的算法里面有环。具有这种循环的无锁算法可能导致一个线程处于饥饿状态。如果另一个线程以"错误"的时间执行操作线程可能会取得进展，而第一个线程必须不断地重试其操作。避免这个问题的数据结构是无等待和无锁定的。

无等待：无等待数据结构是一种无锁数据结构，具有每个访问数据结构的线程都可以在有界的步骤数。可以由于与其他线程发生冲突，导致重试次数无限制因此不能免费等待。

有了这些定义，我认为我的描述就像是锁定自由；）。但对于你的哈希图，我的投票是基于锁的代码。同样在那本书中，作者实现了这样的哈希表，并将其插入到他的书