Acortamiento/Rehash Uuid

Question

primero de todo, quiero asegurarles que soy consciente del hecho de que rehash es un tema sensible.Sin embargo, me gustaría escuchar algunas de sus opiniones, ¿qué actitud tomaría aquí.

Estoy construyendo una aplicación distribuida, donde los nodos de forma remota crear entidades identificadas por un UUID.Finalmente, todas las entidades deben ser recogidos en un dedicado de drenaje nodo, que almacena todas las entidades por el uso de estos Uuid.

Ahora quiero crear identificadores adicionales, que son más útiles para los usuarios humanos.Base64-codificación de los Uuid seguiría crear Identificadores con 22 caracteres, lo cual no es apropiado para el uso humano.Así que necesito algo así como la URL de los servicios de acortamiento.La aplicación de bijective funciones no ayuda, ya que no se puede reducir el valor de la información.Por supuesto, estoy consciente de que tengo que perder la información en el fin de acortar la id.Y también soy consciente de que cualquier reducción de la información de un hash aumentará la probabilidad de colisión.Estoy atascado, ¿cuál es la manera más adecuada para reducir la información a fin de crear identificadores más cortos para los seres humanos.

Aquí están algunos requisitos:Yo le proporcionan la capacidad de mapa {UUID, acortado ID} a través de mi de almacenamiento de datos.Estaría todavía prefieren una no-solución centralizada.Yo probablemente nunca alguna vez necesita más de un millón de Id (~2^20) en total.

Aquí están los pensamientos que se me ocurrió hasta ahora:

• Auto incrementa Id: Si yo tendría que utilizar algún tipo de incremento automático de identificación, podía transferir este id a un ofuscado cadena y pasar este alrededor.Este sería el enfoque más sencillo, y como hay unas llaves, las llaves no sería muy larga.Sin embargo, yo tendría que introducir una entidad centralizada que en realidad no quiero.
• Acortar el UUID: Yo podría tomar algunos de los bits de la original de 128 bits uuid.Entonces debo tomar al menos en cuenta la versión de los UUID.O hay nada de malo con esto?
• Repetir constantemente el UUID: Yo podría aplicar un segundo algoritmo de hash en mi inicial UUID y almacenar la cartografía.

Hay otros enfoques?Lo que es favorable?

Gracias de antemano!

Answer 1

1) acortar el UUID, usted puede simplemente XOR la mitad superior con la parte inferior (y repetir hasta que sea lo suficientemente corto como para usted).Esto para conservar las características de la distribución.Al igual que cualquier solución que se acorta la salida, además de aumentar la posibilidad de colisión debido a la paradoja de cumpleaños

2) XOR asciende a un trivial de hash, pero dado que no se requiere un mezclado adicional que se necesita, está bien.Usted podría utilizar un CDN o noncryptographic hash en el UUID, pero no creo que sea ninguna mejora.

3) Si usted está dispuesto a aceptar algunos la administración central, no tiene que ser doloroso.Una autoridad central puede repartir medianas bloques de espacio de direcciones a cada cliente, entonces el cliente puede recorrer que subrango cuando la asignación de ID.Esto garantiza que no hay colisiones, pero también evita que un viaje redondo para cada ID.Una forma de hacerlo sería utilizar un entero de 32 bits para el IDENTIFICADOR, repartir un bloque de 16 bits a la vez.En otras palabras, el primer cliente se pone manos 0001, que permite 00010000 a 0001FFFF.

4) Se puede insertar en la base de datos con un UUID, pero también tiene un campo de identidad.Esto proporcionaría una alternativa, más compacto único de IDENTIFICACIÓN, que puede ser limitado a 32 bits int.

Answer 2

¿Usted ha considerado el uso de un enfoque aliasing externo, en el que elegir un diccionario de términos amistosos humanos y utilizarlos para hacer (partes de) el UUID más legible:

de305d54-75b4-431b-adb2-eb6b9e546013

El uso de un diccionario de 65.536 palabras, podría llegar a ser:

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

Es poco probable que los usuarios verán la colisión de hash mentales (cebra que ocurre dos veces) con estos nombres legibles por humanos y su base de datos no crece en tamaño. La traducción es biyectiva y puramente interfaz de usuario.

Answer 3

Sólo un par de cosas que aparecen en la mente:

¿Cuál es su caso de uso? Si su preocupación es que va a generar identificadores de manera distribuida, una solución consiste en asignar a cada máquina que es propio y único ID int y usar eso como un prefijo o sufijo en sus documentos de identidad.

Esto no ayuda si al no tener una entidad central que quiere decir nada de lo que hace un seguimiento de las identificaciones, incluso a nivel local. Usted puede pedir prestado una página del mismo UUID y utilizar la hora del sistema en conjunto con el ID de la máquina asignada como anteriormente. Esto se conseguiría hasta 64bits + cualquiera que sea el tamaño de su ID de la máquina era. Básicamente, este es el esquema de UUID V1, salvo que estés usando algo más corta que la dirección MAC para el ID de la máquina. Teniendo en cuenta que sabe que puede comenzar en fechas> = 12 febrero de 2010, usted puede ser capaz de acortar aún más.

Salida la entrada de Wikipedia UUID si no lo ha hecho, puede obtener una idea o dos desde allí sobre cómo construir su propio.

Answer 4

Aquí es un simple algoritmo de hash que escribí. Se podría utilizar este ... se puede cambiar fácilmente las asignaciones de entrada y de salida, y la longitud de la almohadilla para el comercio fuera de la legibilidad vs probabilidad de colisión.

Este algoritmo no está diseñado para ser seguro o que eficiente, pero debe hacer el truco.

public class HashTools {

  final static String inputMapping = "0123456789ABCDEF";

  final static String[] outputMapping = new String[] {
      "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H",
      "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"
  };

  /* Input: String - containing mostly letters / numbers
   * Output: <hashLength> String using 0-9,A-Z encoding
   */
  public static String simpleHash(String str, int hashLength) {
    StringBuilder hashStr = new StringBuilder(hashLength);
    String strUpper = str.toUpperCase();
    int[] hash = new int[hashLength];

    int i, j, num;
    for (i = 0; i < strUpper.length(); i++) {
      char strChar = strUpper.charAt(i);
      num = mapCharToInt(strChar);

      j = i % hashLength;
      hash[j] += num;
    }

    for (i = 0; i < hashLength; i++) {
      hashStr.append(mapIntToHashChar(hash[i]));
    }

    return hashStr.toString();
  }

  private static int mapCharToInt(char hexChar) {
    return inputMapping.indexOf(hexChar);
  }

  private static String mapIntToHashChar(int num) {
    return outputMapping[num % outputMapping.length];
  }
}