13.1 Introduction

In earlier chapters, we studied how to extract parallelism from data structures like queues, stacks, and counters, that seemed to provide few opportunities for parallelism. In this chapter we take the opposite approach. We study concurrent hashing, a problem that seems to be "naturally parallelizable" or, using a more technical term, disjoint-access-parallel, meaning that concurrent method calls are likely to access disjoint locations, implying that there is little need for synchronization.

Hashing is a technique commonly used in sequential Set implementations to ensure that contains(), add(), and remove() calls take constant average time. The concurrent Set implementations studied in Chapter 9 required time linear in the size of the set. In this chapter, we study ways to make hashing concurrent, sometimes using locks and sometimes not. Even though hashing seems naturally parallelizable, devising an effective concurrent hash algorithm is far from trivial.

As in earlier chapters, the Set interface provides the following methods, which return Boolean values:

• add( x) adds x to the set. Returns true if x was absent, and false otherwise,

• remove ( x) removes x from the set. Returns true if x was present, and false otherwise, and

• contains( x) returns true if x is present, and false otherwise.

When designing set implementations, we need to keep the following principle in mind: we can buy more memory, but we cannot buy more...