Ассоциативный массив: Hash-таблица

Одной из часто используемых реализаций ассоциативного массива является hash-таблица.
Важной особенностью является сложность выполнения операций добавления, удаления и поиска - O(1) - другими словами, сложность алгоритма не зависит от количества элементов в массиве - хоть 10 элементов, хоть 10 млн.

Задачка: русская рулетка

Давайте сыграем в русскую рулетку. Вы привязаны к стулу и не можете встать. Вот револьвер. Вот его барабан - в нем шесть гнезд для патронов, и они все пусты. Смотрите: у меня два патрона. Вы обратили внимание, что я их вставил в соседние гнезда барабана? Теперь я ставлю барабан на место и вращаю его. Я подношу револьвер к вашему виску и нажимаю на спусковой крючок. Щелк! Вы еще живы. Вам повезло! Сейчас, до того как мы начнем обсуждать присланное вами резюме, я собираюсь еще раз нажать на крючок. Что вы предпочитаете: чтобы я снова провернул барабан или чтобы просто нажал на спусковой крючок?

Java:: Shift vs Multiply

Читая Effective Java 2nd edition обнаружил любопытную заметку:

The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance:
31*i==(i<<5)-i. Modern VMs do this sort of optimization automatically.

Задачка: непарное число в массиве

Есть массив целых чисел, в котором каждое число встречается дважды, кроме одного.
Не создавая дополнительных структур определить это число за линейное время.

Задачка: Хитрый мальчик задумал 3 числа

Маленький мальчик задумал три числа x, y и z ∈ N.
Можно задать дважды вопрос вида: чему равно значение

a * x + b * y + c * z = ?

где a, b и c ∈ N
Какие нужно задать вопросы мальчику, чтобы узнать задуманные им числа ?

Задача: средняя зп

Три работника хотят узнать свою среднюю зар. плату, но согласно корпоративному этикету её нельзя говорить. Они могут общаться между собой, обмениваться записками, но только так, чтобы никто в конце концов не узнал чужую зп.
Как им необходимо действовать в данной ситуации.