Индивидуальная функция хеширования на основе количества элементов

Question

Я хотел бы разработать хеш-функцию, которая получает объект BitSet и генерирует значение хеш-функции на основе числа 1 в BitSet.Это число рассчитывается с использованием:

BitSet b = new Bitset();
int card = b.cardinality();

Например:

110
1
010
111

Мне нужна карта, которая возвращает элементы в следующем порядке:

1
010
110
111

или

010
1
110
111

Допустим, у вас есть только утилита TObjectIntCustomHashMap:

map = new TObjectIntCustomHashMap<BitSet>( new HashingStrategy<BitSet>() {
            @Override
            public int computeHashCode( BitSet str ) {
                return System.identityHashCode( str );
            }

            @Override
            public boolean equals( BitSet str1, BitSet str2 ) {
                return (str1.cardinality() < str2.cardinality());
            }
        });

, но результат не такой, как ожидалось.

Answer 1

чтобы ответить вам, даже я думаю, что @MathBunny прав ... лучше использовать выделенную структуру, которая обрабатывает ваши требования, чем использовать побочный эффект текущей реализации hashmap ... вот что вы ищете

public class HashTest {
    public static class BitSet extends java.util.BitSet {

        private static final long serialVersionUID = 4014851086683360760L;

        public BitSet(int i) {
            super(i);
        }

        public BitSet() {
            super();
        }

        @Override
        public int hashCode() {
            return stream().map(i -> (int) Math.pow(2, i)).sum();
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof java.util.BitSet) {
                return obj == null ? false : obj.hashCode() == hashCode();
            } else {
                return false;
            }
        }
    }

//  1
//  010
//  110
//  111
    public static void main(String[] args) {
        BitSet bitset1 = new BitSet(1);
        bitset1.set(0);
        BitSet bitset2 = new BitSet(3);
        bitset2.set(1);
        BitSet bitset3 = new BitSet(3);
        bitset3.set(1);
        bitset3.set(2);
        BitSet bitset4 = new BitSet(3);
        bitset4.set(0);
        bitset4.set(1);
        bitset4.set(2);
        Map<BitSet, String> map = new HashMap<>();
        map.put(bitset1, "bitset1");
        map.put(bitset2, "bitset2");
        map.put(bitset3, "bitset3");
        map.put(bitset4, "bitset4");
        map.forEach((k, v) -> System.out.println(v));

    }

}

Answer 2

Я думаю, что самое чистое решение, созданное на основе user93335240, это применить пользовательский компаратор к TreeSet, допускающему O(nlogn) решение, подобное этому:

Set<Integer> t = new TreeSet<>((a, b) -> { a.cardinality() - b.cardinality() });
t.forEach((a) -> System.out.println(a));

Где вы бы создали свою собственную оболочку дляобеспечивает функциональность cardinality().

Вы не можете использовать хеширование, поскольку оно не гарантирует распределение значений hashCode при столкновениях.Вы можете попробовать что-то вроде линейного зондирования, но это не гарантирует, что это будет правильно.

На самом деле, это было бы опровержением нижней границы модели, основанной на сортировке сравнения , если бы вы получили решение O(nlogn).