Вопрос про 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]

1. Действительно ли он должен extends Map?
2. Наеюсь, что 1 - нет, тогда нужен список операций - типа get, put, remove, get/setLimit, getSize, whatever.

[alf-kadett.livejournal.com]

В чём лежит 64-битное число? byte[8]?

[k-79.livejournal.com]

Пускай "толпы объектов" в LinkedHashMap тебя не пугают: для каждого элементарного типа данных (типа int, и т.п.) существует свой объект-контейнер. Упаковывай свои данные в контейнеры и суй их в LinkedHashMap, и будет тебе щастье.

ЗЫ: На Джаве я уж года три как ничего не программал, так что ни разу уже не эксперт.

[avysk]

Почему 1 — нет? Зачем же мне руками кодировать функциональность, которая уже есть в существующем классе? А 64-битное число-ключ хранится таки да, в byte[8].

[avysk]

Ты провёл в караване лето, так что знаешь о них больше меня! :-) Я не очень понимаю, как и куда мне упаковывать значение, которое byte[6]...

[alf-kadett.livejournal.com]

Это хитрость: отношение IS-A - это всегда головная боль. HAS-A рулит :)

[avysk]

Да.

[alf-kadett.livejournal.com]

byte[6] IS-A Object - упаковывать его не надо.

[avysk]

А нельзя мне вот тут понятным языком?

[alf-kadett.livejournal.com]

Дело в том, что массивы - они объекты, но убогие:

    public static void main(String[] args) {
        if (new byte[] {0, 1, 2, 3}.equals(new byte[] {0, 1, 2, 3}))
            System.out.println("same");
        else
            System.out.println("different");
    }

Выводит, очевидно, different.

[alf-kadett.livejournal.com]

Более того:

    public static void main(String[] args) {
        System.out.println(new byte[] {0, 1, 2, 3}.hashCode());
        System.out.println(new byte[] {0, 1, 2, 3}.hashCode());
    }

выводит разные значения.

[alf-kadett.livejournal.com]

То есть просто унаследоваться нельзя - надо менять семантику вызовов. А это гарантирует головную боль.

Я сейчас дотестирую классик и вышлю.

[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);
        }
    }
}

[alf-kadett.livejournal.com]

Понятным языком: любую функциональность можно использовать двумя способами:
1. Унаследоваться от класса
2. Сложить объект этого класса в поле и использовать его

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

[alf-kadett.livejournal.com]

Ну и, очевидно, при наследовании ты получаешь не только поведение - что хорошо и приятно, но и контракт - что не всегда приятно.

[vvindy.livejournal.com]

А кто будет хэш вычислять java? Я не уверен что тебе нужен Map, так как это для храния парных данных типа
Имя -> телефон и внитри для этой пары жава вычислит хэш
добавляют вот так
put(Object key, Object value) или
put( "Вася", "+35850123456" )
http://java.sun.com/j2se/1.3/docs/api/java/util/HashMap.html

тебе это надо? Если нет, то пользуйся HashSet
http://java.sun.com/j2se/1.3/docs/api/java/util/Set.html

используй для получения хэш кода
public int hashCode()
Returns the hash code value for this set.
http://java.sun.com/j2se/1.3/docs/api/java/util/AbstractSet.html#hashCode()

[avysk]

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

[avysk]

Нет, мне нужны именно пары: исходное 64-битное состояние - вычисленное по нему 48-битное. Чтобы не считать каждый раз, потому что многие 64-битные состояния будут повторяться. Или я чего-то не понимаю?

[avysk]

Но в моём случае мне как раз и нужен объект, который будет являться как раз LinkedHashMap. Я же предлагаю наследование просто ради того, чтобы метод переопределить, не меняя никаких интерфейсов к классу — чем в этом случае наследование плохо?

[alf-kadett.livejournal.com]

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

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

[avysk]

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

[alf-kadett.livejournal.com]

Хм. Я тормоз, да. Твой вариант должен работать как часы. Вот мой, вроде работает. Как видишь, чистый LinkedHashMap, без изменений:

package spb.dev2dev.avysk;

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

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

    public static void main(String[] args) {
        LongMap map = new LongMap();
        map.put(new byte[] {1, 2, 3, 4, 5, 6, 7, 8,},  new byte[] {1, 2, 3, 4, 5, 6,});
        map.put(new byte[] {2, 2, 3, 4, 5, 6, 7, 8,},  new byte[] {2, 2, 3, 4, 5, 6,});
        map.put(new byte[] {3, 2, 3, 4, 5, 6, 7, 8,},  new byte[] {3, 2, 3, 4, 5, 6,});
        map.put(new byte[] {4, 2, 3, 4, 5, 6, 7, 8,},  new byte[] {4, 2, 3, 4, 5, 6,});
        map.put(new byte[] {5, 2, 3, 4, 5, 6, 7, 8,},  new byte[] {5, 2, 3, 4, 5, 6,});

        print(map.get(new byte[] {1, 2, 3, 4, 5, 6, 7, 8,}));
        print(map.get(new byte[] {2, 2, 3, 4, 5, 6, 7, 8,}));
        print(map.get(new byte[] {3, 2, 3, 4, 5, 6, 7, 8,}));
        print(map.get(new byte[] {4, 2, 3, 4, 5, 6, 7, 8,}));
        print(map.get(new byte[] {5, 2, 3, 4, 5, 6, 7, 8,}));
    }

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

    public byte[] get(byte[] key) {
        return (byte[]) storage.get(toLong(key));
    }

    public byte[] remove(byte[] key) {
        return (byte[]) storage.remove(toLong(key));
    }

    public byte[] put(byte[] key, byte[] value) {
        return (byte[]) storage.put(toLong(key), value);
    }

    private static Long toLong(byte[] a) {
        long result = 0L;
        for (int i = 0; i < a.length; i++) {
            result <<= 8;
            result |= a[i];
        }
        return Long.valueOf(result);
    }

    private static void print(byte[] a) {
        if (a==null) {
            System.out.println("null");
            return;
        }

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");
        }
        System.out.println();
    }
}

[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 :)

[alf-kadett.livejournal.com]

    private static Long toLong(byte[] a) {
        long result = 0L;
        for (int i = a.length; --i >= 0;) {
            result <<= 8;
            result |= a[i];
        }
        return Long.valueOf(result);
    }

будет чуток быстрее, а порядок байтов тебе тут всё равно не важен.

[avysk]

Вот в этом примере подставить:

map.put(new byte[] {-128, -128, 0, 0, 0, 0, 0, 0,}, new byte[] {0, 0, 0, 0, 0, 0,});
map.put(new byte[] {96, -128, 0, 0, 0, 0, 0, 0,}, new byte[] {32, 0, 0, 0, 0, 0,});

print(map.get(new byte[] {-128, -128, 0, 0, 0, 0, 0, 0,}));

Результат — 32, 0, 0, 0, 0, 0. :(

Что я делаю не так?

[avysk]

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

[avysk]

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

[alf-kadett.livejournal.com]

Это я облажался c приведением типов. Поправь метод:

    private static Long toLong(byte[] a) {
        long result = 0L;
        for (int i = 0; i < a.length; i++) {
            result <<= 8;
            result |= (0xffL & a[i]);
        }
        return Long.valueOf(result);
    }

Дело в том, что result |= a[i]; эквивалентно result = result | a[i];, а это значит, что a[i] будет приведено к long. Поскольку byte в Java signed, то -1 в конце массива угробит весь наш ключ.

[alf-kadett.livejournal.com]

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

[alf-kadett.livejournal.com]

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

[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;
    }

[avysk]

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

[alf-kadett.livejournal.com]

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

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