Вопрос про Java

[avysk]

Други, а кто понимает в Java? (Особую надежду возлагаю на k_79.) Расскажите мне понятными словами, как бы мне сделать хэш, который бы в качестве ключа использовал 64-битное число, значение выдавал 48-битное (а лучше сразу byte[6]), а ещё был фиксированного размера и при превышении оного старые записи удалял? Про LinkedHashMap я читал, но ничего толком не понял. Там объекты какие-то толпами, а у меня просто числа...

Я вот пробовал породить класс, который extends LinkedHashMap<Long, byte[6]>,
и метод removeEldestEntry или как его там переопределил правильно. Из своего 64-битного числа я генерю Long, а в свои массивы запиываю то, что даёт get(мойключ), и если дал null, то тогда массив руками считаю и в хэш запихиваю посредством put(мойключ, посчитанныймассив). И ничего не получается — какие-то бредовые результаты, совсем всё не так, как если бы каждый раз руками массив считать.

Что делать-то, а? Только я Java не знаю, и программировать на ней не умею.

Comments

[alf-kadett.livejournal.com]

package spb.dev2dev.avysk;

import java.util.Map;
import java.util.LinkedHashMap;
import java.util.Arrays;

/**
 * @author alf
 */
public class LongMap {
    private static int SIZE_LIMIT = 50;

    private Map storage = new LinkedHashMap() {
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > SIZE_LIMIT;
        }
    };

    public byte[] get(byte[] key) {
        ByteBag bag = (ByteBag) storage.get(new ByteBag(key));
        return bag == null ? null : bag.getValue();
    }

    public byte[] remove(byte[] key) {
        ByteBag bag = (ByteBag) storage.remove(new ByteBag(key));
        return bag == null ? null : bag.getValue();
    }

    public byte[] put(byte[] key, byte[] value) {
        ByteBag oldBag = (ByteBag) storage.put(new ByteBag(key), new ByteBag(value));
        return oldBag == null ? null : oldBag.getValue();
    }

    // add size() and other methods if necessary

    private static class ByteBag {
        private byte[] value;

        public ByteBag(byte[] value) {
            this.value = value;
        }

        public byte[] getValue() {
            return value;
        }

        public boolean equals(Object obj) {
            ByteBag bb = (ByteBag) obj;
            return Arrays.equals(value, bb.getValue());
        }

        public int hashCode() {
            return Arrays.hashCode(value);
        }
    }
}

[avysk]

Спасибо! Вот только как там с быстродействием — меня смущает вызов ByteBag.equals, который, пожалуй, происходит по каждому чиху, нет? У меня хэш размером не 50, а, скорее, 1000000. Мне с моими сишными привычками несколько диковато это всё для того, чтобы просто использовать 64-битный ключ... Не быстрее будет собрать из ключа Long?

[alf-kadett.livejournal.com]

О чихах - для поиска ты берёшь хэшкод ключа (вызов ByteBag.hashCode()), выбираешь корзину, линейно ищешь по ней (один или несколько вызовов ByteBag.equals())

С лонгом будет быстрее, да... Наверное. Может быть :)

[avysk]

А ByteBag.hashCode() будет одинаковым для разных ByteBag с одним содержимым? А почему? А почему для массивов разный?

[alf-kadett.livejournal.com]

Да, одинаковый для одинаковых массивов:

    // Arrays.java, jdk1.5.0_07
 
    public static int hashCode(byte a[]) {
        if (a == null)
            return 0;
 
        int result = 1;
        for (byte element : a)
            result = 31 * result + element;
 
        return result;
    }

Для массивов хэшкод считается как для Object - это (очень грубо) внутренный адрес объекта.

Почему в Java так сделано - не знаю, потому и написал ByteBag. А вот вариант c Long надо погонять ещё - я знаю, что ByteBag является "правильным" ключом, то есть мы точно не слепляем значения. А вот в методе toLong надо проверить, что он не теряет биты.

Так что в обычной жизни я бы плюнул на производительность и остался с ByteBag :)

[avysk]

Мда. Похоже, что теряет. Смотри пример ниже. Мда. Что же это за язык программирования такой, в котором без выкрутасов хэш с 64-битным ключом не сделать? ;((

[avysk]

И как я могу быть уверен, что в ByteBag ничего не слепится?

[alf-kadett.livejournal.com]

В случае ByteBag *HashMap опирается на Arrays.equals, который по контракту сверяет каждый байт.

[alf-kadett.livejournal.com]

    public static boolean equals(byte[] a, byte[] a2) {
        if (a == a2)
            return true;
        if (a == null || a2==null)
            return false;

        int length = a.length;
        if (a2.length != length)
            return false;

        for (int i = 0; i < length; i++)
            if (a[i] != a2[i])
                return false;

        return true;
    }

[alf-kadett.livejournal.com]

Но вообще я всё разлепил, так что можно жить с лонгами.

[avysk]

Спасибо, всё заработало!

[alf-kadett.livejournal.com]

Ну, типа фирменное - Enjoy IT!

И привет Лаперье, ага.