Java - Язык:получить уникальное свойство объекта (например, хэш-код, но защищенный от столкновений)

StackOverflow https://stackoverflow.com/questions/1843565

  •  12-09-2019
  •  | 
  •  

Вопрос

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

Одна идея:Запишите хэш-код каждого объекта в мультимножество.Затем используйте хэш-коды в качестве уникального идентификатора, но если этот хэш-код присутствует в наборе более одного раза, используйте другое значение, которого также нет в наборе.Но это кажется громоздким и неуклюжим.

Идеи получше?

Вот что у меня уже есть:

public static <V> void toGraphViz(final Graph<V, DefaultWeightedEdge> g, String filename) {

    // to avoid hashcode collisions
    final Set<Integer> hashcodes = new HashSet<Integer>(g.vertexSet().size());

    DOTExporter<V, DefaultWeightedEdge> dot = new DOTExporter<V, DefaultWeightedEdge>(new VertexNameProvider<V> () {

    // vertex name must be unqiue
    @Override
    public String getVertexName(V arg0) {
        int hash = arg0.hashCode();
        while (hashcodes.contains((hash))) {
            hash += 1;
        }
        return "" + hash;
    }
}

Редактировать: Я предполагаю, что изначально это не было ясно, но идентификационный номер каким-то образом должен быть функцией объекта, потому что getVertexName(V) будет вызван несколько раз, и он ожидает, что для одних и тех же значений V, он получит те же результаты.

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

Это было полезно?

Решение

Каково время жизни этого уникального номера?Просто срок службы программы?В таком случае, почему бы не использовать простой статический счетчик в классе, доступ к которому осуществляется с подходящей синхронизацией?Увеличивайте его для каждого нового объекта.Нет необходимости вести список использованных вами значений, просто самое высокое значение, которое вы использовали.

Если он уникален во многих исполнениях (и, возможно, во многих одновременных экземплярах), то, возможно, вы можете просто использовать базу данных, которая генерирует идентификаторы записей unqiue.

ОТРЕДАКТИРОВАНО в ответ на разъяснение

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

Я думаю, что работа с хэш-кодом класса, в котором будут возникать коллизии, усложняет жизнь.Предполагая, что мы можем полагаться на то, что рассматриваемые классы вершин правильно реализовали equals(), тогда мы можем использовать сам объект в качестве ключа к набору хэш-кодов, которые мы использовали.

public class Hasher {

    public  <V> void toGraphViz(final Graph<V, DefaultWeightedEdge> g, String filename) {
         final Map<V, Integer> hashcodes = new HashMap< V, Integer>();
         final int latestHashHolder[] = { 0 }; // array to allow access from inner class

         DOTExporter<V, DefaultWeightedEdge> dot 
                 = new DOTExporter<V, DefaultWeightedEdge>(new VertexNameProvider<V> ()) {

         // vertex name must be unqiue
            @Override
            public synchronized String getVertexName(V vertex) {
                int hashcode;
                if ( hashcodes.containsKey(vertex)){
                    hashcode = hashcodes.get(vertex);
                } else {                
                    hashcode = latestHashHolder[0];
                    latestHashHolder[0]++;
                    hashcodes.put(vertex, (Integer)latestHashHolder[0]);
                }
                return "Vertex-" + hashcode;
            }
        };
    }
}

Другие советы

Вы могли бы рассмотреть возможность использования UUID ( идентификатор пользователя ), в зависимости от того, чего вы пытаетесь достичь...

Чтобы найти уникальное значение для объекта, вы должны знать комбинацию свойств, которые делают объект уникальным.

Чтобы запустить ".contains()", вам нужно иметь метод определения ".equals()", что означает, что вы уже должны знать, как однозначно идентифицировать Вершину, поэтому, возможно, вы сможете придумать выражение уникальных свойств?

например, "(x, y, z, rgb)".

Если я не неправильно понимаю вопрос, я бы не рекомендовал использовать хэш-код объекта для этой цели.

Почему бы просто не использовать серийный номер?

static private int serial=0;
static public synchronized nextSerialNumber() { return ++serial; }

Или комбинация / гибрид, скажем, длинный из ((хэш<<32) | getNextSerial()).

Чтобы обратиться к разъяснению РЕДАКТИРОВАНИЯ

Когда вы создаете объект, присвоите серийный номер закрытой переменной-члену и верните его для hashCode().Затем вы должны переопределить equals с помощью вызова super.equals() (поскольку сгенерированный серийный номер соответствует реализации equals() по умолчанию), потому что переопределение hashCode() без соответствующего переопределения equals() приведет к повторному отображению кода для tools (и других программистов).

public class Vertex
{
private final int                   serial;                                 // instance serial number

public Vertex() {
    serial=nextSerialNumber();
    ...
    }

public int hashCode() {
    return serial;
    }

public boolean equals(Object obj) {
    return super.equals(obj);                                               // serial number hash-code consistent with default equals    
    }

...        

static private int nextSerial=0;
static public synchronized nextSerialNumber() { return nextSerial++; }
}

Я думаю, вы неправильно поняли хэш-код.Основываясь на контракте, hascode должен быть одинаковым, когда equals(..) имеет значение true и наоборот.Таким образом, в вашем случае только вершина с одинаковыми свойствами должна иметь одинаковый hascode, в противном случае ваш самостоятельно написанный метод вычисления hascode должен быть исправлен.Насколько я понял ваш вопрос, вершина сама по себе уникальна, так что у вас не должно возникнуть проблем, верно?

Я, вероятно, не понимаю, что вы делаете, но подумайте о создании ссылки на каждый объект.Поскольку ссылка содержит адрес объекта, она будет уникальной для каждого объекта.

Это не так уж сложно, не так ли?Просто используйте другой алгоритм хэширования, если тот, что в Java, не гарантирует отсутствия коллизий.Отправьте объект хэш-алгоритму, напримерSha-256, и используйте это в качестве ключа.Если вам нужно сохранить разные копии одного и того же объекта с разными значениями хэша, используйте начальное значение при выполнении хэша и сохраняйте это, связанное с объектом, с помощью хэша.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top