Получается, у двух объектов с одинаковым hashCode hashCode1 и hashCode2 будут одинаковыми. Это перечёркивает всю идею двойного хэширования по сравнению с обычной открытой адресацией (с линейным пробированием). Функция для второго хэшкода должна предоставляться снаружи, как и для первого. Можно попробовать применить подход, используемый для SortedMap (сделать что-то аналогичное Comparatorу и Comparable для второго хэша).

2. Hashtable/src/HashTable.java

   Line 21 in 2d9cdf0

   private int lastSize;

Это поле не используется.

3. Вы сделали thread-safe класс, путём добавления synchronized ко всем методам. Он действительно стал thread-safe, но большого смысла в этом нет: можно сделать мапу со всеми синхронизированными методами из любой мапы с помощью стандартной библиотеки (java.util.Collections.synchronizedMap()). Навязывать синхронизацию не стоит, часто потокобезопасность не нужна и лишний оверхед просто так добавлять не стоит.

4. Кстати, о потокобезопасности: тот тест, где вы пытаетесь проверить многопоточность на самом деле не многопоточный: Thread.run() не создаёт новый поток. А если б он был многопоточным, то, скорее всего, не проходил бы, или проходил бы не всегда: assertEquals мог бы вызваться до завершения thread1 и thread2. interrupt там вообще непонятно зачем.

5. equals по спецификации интерфейса Map должен уметь делать сравнение с другими реализациями Map. hashSet, кстати, тоже проверьте на соответствие спеке.

6. Логика equals реализована неправильно: если obj содержит все элементы из this и ещё некоторые, то ваш equals вернёт true

7. В setDeleted нет необходимости инициализировать массив в цикле. После создания там и так будут false.

8. Логику массива deleted, кстати, я не понял. По-моему, после rehash не должно быть deleted элементов вообще. Вообще, мне кажется deleted может быть нужен, если элемент в ячейке был, но мы его удалили, чтобы продолжить поиск по цепочке в случае коллизии. Но у вас, как будто что-то другое. Или нет?

9. Что за параметр link в одном из конструкторов?

10. Почему hashCode тестируется через println. Поведение hashCode для Map специфицировано, можно проверить с помощью assertEquals

11. Что произойдёт, если после вычисления хэшей нужно положить элемент в последнюю ячейку, а она занята? Обычно в хэш-таблицах с открытой адресацией пытаются вставить в начале массива (по кругу). У вас такой логики нет.

12. Избавьтесь от сырых типов везде: в HashSet и в тестах.

13. Имена у contains и getIndex вводят в заблуждение. Я так понял, getIndex возвращает подходящий свободный индекс для ключа, а contains как раз возвращает индекс для ключа, который есть в мапе.

14. В rehash лишний раз копируете массив. Вспомните, как работают ссылки в Джаве. Одной копии можно избежать.

15. Вместо констант KEYS/VALUES лучше сделать перечисление.

16. Разберитесь с тем, какие методы должны быть публичными: getIterator, например, не должен. Возможно есть что-то ещё.

Фууу!!! Файлы идеи оставил, грязно, приберись!