Быстрый способ создать уникальный идентификатор строки / ключ из известного набора потенциальных идентификаторов в JavaScript

Question

Допустим, вы хотите иметь набор из 1–2-значных шестнадцатеричных чисел, то есть 256 чисел.Просто используйте небольшой набор для решения проблемы, но он будет работать со строкой любого размера.

Таким образом, у вас есть потенциал N или 256 чисел в этом случае.Вы собираетесь «генерировать» новый идентификатор для каждой новой записи данных, которая появляется на вашем пути.Таким образом, он начинает и случайным образом дает вам af, затем 1d, затем 8a и т. Д.

Простой наивный способ сделать это - просто сгенерировать все числа по порядку, затем перемешатьих, и просто выскочить из набора.Это прекрасно работает, когда у вас есть только 256 номеров.Но если у вас есть миллионы или миллиарды номеров, это нецелесообразно, так как у вас может быть много сгенерированных идентификаторов, которые не используются в течение длительного времени.Я хотел бы избежать этого.

Поэтому мой вопрос в том, каков или самый быстрый способ создания уникальной ключевой строки, подобной этой, без генерации всех их заранее и без упорядочения, просто увеличивая на 1или еще много чего.То есть ключ должен казаться случайным.

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

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

Может быть, есть способ сортировки случайным образом (и генерации) три сразуи таким образом сгенерируйте идентификатор, так как вы окажетесь в уникальном случайном месте в дереве.Возможно, что-то в этом роде, я не знаю.

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

Answer 1

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

Шифрование будет выполнено на счетчике в виде двоичного числа, а зашифрованный результат с большинством алгоритмов будет того же размера, также двоичного.При желании вы можете закодировать результат с помощью base-64 или hex, чтобы его было проще использовать в качестве символьной строки.

Поскольку шифрование должно быть биекцией (то есть сопоставлением «один к одному»),чтобы расшифровка была возможной, это гарантированно будет давать разные результаты каждый раз, пока общее число идентификаторов не переполнится.Если это разумная функция шифрования, то результат будет выглядеть случайным (в противном случае шифр будет уязвимым).

Answer 2

Я рассматриваю что-то вроде этого:

var trie = buildTrie()
var id1 = genId(trie)
var id2 = genId(trie)

console.log(id1,id2)

function buildTrie() {
  var trie = buildNode(0)
  return trie

  function buildNode(level) {
    if (level == 7) { // 8 bits
      var node = {
        available: true,
        leaf: true
      }
      return node
    } else {
      var a = buildNode(level + 1)
      var b = buildNode(level + 1)
      var node = {
        availableLeft: true,
        availableRight: true,
        left: a,
        right: b
      }

      a.parent = node
      b.parent = node

      return node
    }
  }
}

function genId(node) {
  var bytes = []
  step(node, bytes)
  var id = parseInt(bytes.join(''), 2).toString(16)
  return id

  function step(node, bytes) {
    if (node.leaf) {
      node.available = false
      var c = node
      var p = c.parent
      while (p) {
        if (p.left == c) {
          p.availableLeft = false
        } else if (p.right == c) {
          p.availableRight = false
        }

        if (!p.availableLeft && !p.availableRight) {
          c = p
          p = p.parent
        } else {
          p = false
        }
      }
    }

    var randomDirection = Math.random() >= 0.5
    if (randomDirection) {
      if (node.availableLeft) {
        bytes.push(0)
        step(node.left, bytes)
      } else if (node.availableRight) {
        bytes.push(1)
        step(node.right, bytes)
      }
    } else {
      if (node.availableRight) {
        bytes.push(1)
        step(node.right, bytes)
      } else if (node.availableLeft) {
        bytes.push(0)
        step(node.left, bytes)
      }
    }
  }
}

Может быть, есть лучший способ.

Answer 3

Я думаю, что должен быть какой-то компромисс между скоростью, гибкостью и эффективностью.

В случае одного псевдослучайного генератора вы получите равномерное распределение ключей и сможете генерировать его достаточно быстро.Однако проверка существующего идентификатора будет медленной.Вы можете использовать фильтры Блума (сохранение памяти) или попытки, но затем, как вы сказали, в какой-то момент вам следует увеличить пространство.

Другой вариант - использовать Код Грея , который будет выдавать каждый ключ (но не в случайном порядке).Вам необходимо отслеживать последний выданный код.

Answer 4

Я не уверен, насколько это будет эффективно, но моя идея - использовать object или Map и Math.random()

let obj = {}

function generateRandomId(){
  let id = Math.abs( 0.5 - Math.random()) * 1000
  if(obj[id]){
   generateRandomId() 
  } else {
    obj[id] = true
  }
  return id
}

console.log(generateRandomId())
console.log(generateRandomId())
console.log(generateRandomId())
console.log(generateRandomId())

Но если вы согласны с использованием модулей, я считаю, что этот наиболее полезен

uuid это генерирует UCIDS RFC4122.

Answer 5

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

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

Вы получите что-то вроде:

• Запись A => id == 1 => mixed id == 0x7ed55d16
• Запись B => id == 2 => mixed id == 0xc761c23c
• и т. Д.

Здесь можно найти вдохновение:

• https://crypto.stackexchange.com/questions/12145/need-32-bit-mixing-function-that-has-perfect-avalanche-between-octets
• https://gist.github.com/badboy/6267743