I went through http://preshing.com/20130529/a-lock-free-linear-search/ and https://code.google.com/p/nbds/
I can't understand how any of these hashtable are lock fee. I mean if we have two methods on a hashtable getItem and setItem. And this is my function
function increment2(key):
val = hashtable.getItem(key) + 2
hashtable.setItem(val)
Now this function runs in 2 threads, now if I don't use a lock in this function value of hashtable.getItem(key) can be increased by 2 or 4. I am very confused can someone help me in understanding
When talk about concurrent containers, we usually mean that single operation, defined for this container, is atomic. In your case hashtable.getItem(key) and hashtable.setItem(key, val) are atomic operations. E.g. if .getItem() is executed concurrently with .setItem(), then it will return either new value or old value, but not a mix of them.
But concurrent container doesn't garantee, that sequence of two or more its operations is atomic. If user needs atomic property for sequence of operations, he shouldn't expect this property from container's implementation but implement this property by hands. In your case, if you need increment2 function to be atomic, you need to implement this property by yourself.
Lock-based concurrent containers usually can be easy modified for make some sequence of operations to be atomic.
From the other side, lock-free concurrent containers hardly can be extended to have sequence of the operations to be atomic. Lock-free algorithms are very fragile in that sence.