Да, GUID должен всегда быть уникальным. Это основано и на аппаратных средствах и время плюс несколько дополнительных битов, чтобы удостовериться, что это уникально. Я уверен, что теоретически возможно закончиться с двумя идентичными, но крайне маловероятно в реальном сценарии.
Вот большая статья Raymond Chen на Гуидах:
https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx ​ ​ ​
Есть новый профилировщик Java, который в некоторой степени делает то, что вам нужно. CollectionSpy ( www.collectionspy.com ) отслеживает количество внутренних повторных хеширования любого контейнера хеширования, а также имеет графическую визуализацию длин списка корзины. Однако (пока) не предоставляет никакой информации о времени.
Что касается второй части вашего вопроса, если вы ищете быструю реализацию Hashmap с некоторыми приличными гарантиями в реальном времени, посмотрите Javolution . Это быстро, надежно и дает приличное количество деталей о производительности.
TreeMap основан на красно-черном дереве.
Обновление: ] автор интересуется HashMaps, где отдельные цепочки являются бинарными деревьями.