Потому что стандартная реализация equals() для массивов сравнивает их по ссылке, а не по содержимому. HashMap использует методы equals() и hashCode() для сравнения ключей. Если два массива байтов имеют разное содержимое, но одинаковую ссылку, они считаются равными. Если имеют одинаковое содержимое, но разные ссылки, они считаются неравными.
Для корректного использования byte[] в качестве ключа, нужно обернуть его в объект, который переопределяет equals() и hashCode() для сравнения по содержимому. Пример такой обертки:
java