Алгоритм снежинки и разделение таблицы с несколькими ключами

предисловие

В данной статье речь пойдет о генерации серийного номера платформы в платежной системе. В целом мы хотим, чтобы сгенерированные значения полей соответствовали нашим ожиданиям, и стараемся не использовать совершенно нестандартные значения. Допустим, значение серийного номера платформы в нашей платежной системе равно20200627130743000001. Первые 14 цифр этого числа представляют отметку времени, указывающую, что транзакция произошла в 13:7:43 27 июня 2020 г., а последние 6 цифр представляют последовательность в секундах. Значение здесь равно000001, что указывает на то, что это первая транзакция, которая произошла за эту секунду. Можно видеть, что установка правила длины из 6 цифр здесь может удовлетворить не более 1 миллиона транзакций за 1 секунду.

Если вы используете базу данных Oracle, значение последних 6 цифр очень просто, вы можете напрямую использовать механизм последовательности, который поставляется с базой данных. Значения последовательности между узлами не будут повторяться, поэтому в однокластерной распределенной среде нет проблем.

Однако в обычных Интернет-приложениях большинство приложений используют бесплатный Mysql с открытым исходным кодом, который не имеет встроенного механизма последовательности. И большинство сервисов развертываются распределенным образом, поэтому создание уникального идентификатора становится проблемой. Услуги, которые генерируют уникальные идентификаторы в отрасли, также известны как发号器, Это название довольно приземленное, и в этой статье мы хотим не обсудить, как спроектировать общий сервис эмитента номера, а прояснить детали генерации серийного номера платформы в платежной системе.

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

UUID — это сокращение от Universally Unique Identifier, которое может гарантировать уникальность в распределенной системе. Однако нам сложно применить это значение к нашим бизнес-сценариям.Во-первых, самым большим недостатком является отсутствие семантики.Во-вторых, это занимает много места для хранения и не имеет упорядоченности, что скажется на производительности Mysql. при вставке. , читатели заинтересованы в ссылке на другую информацию.

Алгоритм снежинки — это реализация генератора чисел Twitter с открытым исходным кодом, что в переводе с китайского означает «снежинка». Реализовано на языке Scala, адрес Github:snowflake. Эта статья адресована Java-инженерам, я полагаю, что не все будут использовать Scala напрямую в проекте, поэтому он вообще будет перереализован по своему алгоритму. Но многие друзья чувствуют себя очень сложно, как только видят реализацию.Я обобщил причину, потому что я не знаком с бинарными и битовыми операциями. Итак, давайте сначала начнем с основ, а затем предоставим окончательный вариант реализации для ознакомления.

Принцип алгоритма снежинки

Прежде чем приступить к анализу, давайте сначала уточним, что генерирует алгоритм снежинки. Сразу к выводу, в Java это значение типа Long. Все арифметические операции используются для генерации числа типа Long.Кроме того, тип Long представляет собой 64-битный бит, который состоит из 64-битных чисел 0 или 1. Поскольку это конечное число цифр, должно быть максимальное значение и минимальное значение.Давайте посмотрим на представление после преобразования его в двоичное.

/**
 * 转换为二进制，并对其补零，直到达到64位
 */
public static String toBinaryString(long value) {
  String binaryLong = Long.toBinaryString(value);
  while (binaryLong.length() < 64) {
    binaryLong = "0" + binaryLong;
  }
  return binaryLong;
}

После вызова по отдельности получаем:

Long.MAX_VALUEДесятичная дробь9223372036854775807, двоичный файл0111111111111111111111111111111111111111111111111111111111111111

Long.MIN_VALUEДесятичная дробь-9223372036854775808, двоичный код которого1000000000000000000000000000000000000000000000000000000000000000

Вот напоминание:

В 64 битах первый бит представляет плюс или минус 0 + 1 -

Поскольку мы обычно генерируем целые числа без знака, здесь нет необходимости рассматривать отрицательные числа. ОК, тогда я думаю всем понятно, наша цель построить 64-битную последовательность битов, где первый бит равен 0, остальные 63 бита генерируются по определенным правилам, и наконец преобразуются в десятичные числа, чтобы мы получили Длинный тип. Посмотрите, как преобразовать двоичное значение в десятичное. Длинное значение:

/**
 * 二进制转为数值
 */
public static long toLong(String binaryString) {
  return Long.valueOf(binaryString, 2); // 2代表原来的进制
}

Обладая этими знаниями, вы можете ознакомиться с конкретными правилами алгоритма снежинки.

правило

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

Это произведение имеет вышеуказанное предзнаменование, я думаю, оно очень понятно,0фиксированное значение, представляющее положительное число,41Битовые метки времени увеличиваются со временем, что гарантирует, что мы генерируемLongЗначение типа должно быть тем больше, чем позже оно генерируется, то есть увеличивается тенденция с течением времени.10Идентификатор машины с битовым заданием на самом деле очень легко понять, потому что служба развертывается на нескольких узлах, и необходимо определить информацию о машине, на которой работает алгоритм, чтобы при одновременном вызове разных служб, даже если время в миллисекундах точно такое же, значения, генерируемые этими 10 битами, тоже разные. В итоге осталось12Серийный номер биты вы можете посмотреть во введении в начале статьи.000001Последовательность имеет точно такое же назначение, как и эта, поэтому я не буду говорить об этом здесь.

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

время

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

• Что, если текущее время машины изменится?
• Зачем вычитать метку времени начала?

Хорошо, давайте ответим по одному. Если машинное время изменяется, это зависит от того, рано оно или поздно. Если поздно, то все в порядке. Если рано, извините, и вы обнаружите, что могут быть повторяющиеся значения. Это самый большой недостаток этого алгоритма. , Вы должны обратить внимание на проблему часов назад. Чтобы не влиять на бизнес, мы можем сравнить его с меткой времени, используемой последним сгенерированным значением в процессе внедрения, если оно меньше, это означает, что системное время было отозвано и отказ в предоставлении услуги.

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

Что такое System.currentTimeMillis()?

Многие друзья, возможно, использовали его, но не задумывались об этой проблеме, вот прямой ответ:System.currentTimeMillis() 返回从 1970-01-01 00:00:00 到现在过去的毫秒数.

Вы можете не верить, но позвольте мне доказать это:

SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss SSS");
formatter.setTimeZone(TimeZone.getTimeZone("GMT")); //设置为格林威治时间
long begin1970Timestamp =  formatter.parse("1970-01-01 00:00:00 000").getTime();
System.out.println("beginTimestamp : " + begin1970Timestamp);
// 输出结果 beginTimestamp=0

Это должно быть установлено на среднее время по Гринвичу, потому что Китай является восьмым восточным округом, поэтому используйте1970-01-01 08:00:00 000Дело во времени Бытия.

Преобразование метки времени в дату в Java

long currentTimeMillis = System.currentTimeMillis();
System.out.println(currentTimeMillis);
// 1593243941862
System.out.println(toBinaryString(currentTimeMillis));
// 0000000000000000000000010111001011110100101111010011101111100110
Date date = new Date(currentTimeMillis);
System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(date));
// 2020-06-27 15:45:41

Видно, что текущая метка времени получаетсяLongтип, который временно после преобразования в двоичный41немного, вот я следую64Стандарт дополняется нулями.

Хорошо, теперь ответ на вопрос.

Зачем вычитать метку времени начала?

мы все знаем41Длина бита также имеет максимальное значение, т.е.41Кусок1Какая дата после преобразования в временную метку?

long maxTimeMillis = toLong("StringUtils.repeat("1", 41)");
// 或者使用 (1L << 41) - 1L 计算结果是一样的，注意别少了L
System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date(maxTimeMillis)));
// 2039-09-07 23:47:35

ответ2039-09-07 23:47:35, отметка времени, упомянутая выше,1970-01-01Смещение рассчитывается как базовое время. Очевидно, что этот передатчик можно использовать не более69год. Для того, чтобы прояснить эту задачу, приведу следующий расчет:

//返回从 1970-01-01 00:00:00 到现在过去的毫秒数
long currentTimeMillis = System.currentTimeMillis();
//一年有这么多毫秒
long oneYearMs = 365 * 24 * 60 * 60 * 1000L;
//验证一下 执行这段代码的时间是2020年，得到的结果是50
System.out.println(currentTimeMillis / oneYearMs);
// 输出50
//从0递增到最大需要多久呢？没错是 69 年
System.out.println(maxTimestamp/ oneYearMs);
// 输出69

видишь ли, если1970В качестве базового дня2039В следующем году наш номерной передатчик не будет работать. Тогда, если мы возьмем2015год в качестве базовой даты? Понятно, что можно использовать2084год.

Как правило, базовая дата — это самое позднее время системы, потому что чем ближе вы подходите, тем ближе к теоретическому максимальному возрасту. Например, ваш проект2018Годы можно использовать2018-01-01. Здесь мы используем фиксированную дату2015-01-01 00:00:00, его соответствующая временная метка на китайском языке1479692912967.

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

// 起始时间
private static final long snsEpoch = 1479692912967L;
long timestamp =  System.currentTimeMillis();

  // 不允许时钟回拨
  if (timestamp < this.lastTimestamp) {
    throw new RuntimeException(String.format(
        "Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
  }

// 上次生成id的时间戳
lastTimestamp = timestamp;

// 时间部分
long timePart = timestamp - snsEpoch;

информация о машине

информация о машине, реализация в алгоритме будет10Разделен на5битовый центр обработки данных (DATA_ID) бит и5Бит идентификатора машины (WOKER_ID). Позвольте мне сказать кое-что о центре обработки данных, и вы можете это испытать: «три центра в двух местах, аварийное восстановление в разных местах и ​​развертывание между побережьями», вот что это значит. Идентификатор машины на самом деле является уникальным идентификатором машины.Используемый алгоритм является пользовательским, и обычно значение получается путем выполнения арифметической операции с информацией о машине. Как показано ниже, строки IP-адреса и имени компьютера преобразуются в число.

// 数据中心
private static final long DATA_ID = dataIdGen();
// 机器
private static final long WOKER_ID = workIdGen();

/**
 * 数据中心Id，使用hostname（机器名）取余，最大值为5个bit的最大值11111 = 31
 */
private static long dataIdGen() {
  try {
    return getHostId(Inet4Address.getLocalHost().getHostName(), 31);
  } catch (UnknownHostException e) {
    return ThreadLocalRandom.current().nextLong(32);
  }
}

/**
 * 机器Id，使用hostadddress（IP地址）取余，最大值为5个bit的最大值11111 = 31
 */
private static long workIdGen() {
  try {
    return getHostId(Inet4Address.getLocalHost().getHostAddress(), 31);
  } catch (UnknownHostException e) {
    return ThreadLocalRandom.current().nextLong(32);
  }
}

/**
 * 对字符串取余，获得的结果最大为max<br>
 * 为了把字符串变成数字
 */
private static long getHostId(String value, int max) {
  byte[] bytes = value.getBytes();
  int sum = 0;
  for (byte b : bytes) {
    sum += b;
  }
  return sum % (max + 1);
}

последовательность в миллисекундах

Наконец, мы подошли к последней части, последовательности в миллисекундах, которая является ключом к алгоритму, генерирующему число не более чем за 1 миллисекунду. Длина этой части12бит, десятичный максимум4095. от0прибыть4095То есть поддержка в течение 1 миллисекунды4096Ручка. А если превысит? Очень просто дать системе подождать секунду, а затем сгенерировать ее снова в следующую миллисекунду, это просто и грубо.

Хорошо, вот посмотрите на полную реализацию.

// 起始时间
private static final long snsEpoch = 1479692912967L;
// 上次生成id的时间戳
private long lastTimestamp = -1L;
// 序列号（如果同一毫秒并发需要使用）
private long lastSequence = 0L;
// 数据中心
private static final long DATA_ID = dataIdGen();
// 机器
private static final long WOKER_ID = workIdGen();


public synchronized long nextId() {
  long timestamp = timeGen();

  // 不允许时钟回拨
  if (timestamp < this.lastTimestamp) {
    throw new RuntimeException(String.format(
        "Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
  }

  // 上一次请求的时间戳和此刻相等，需要生成序列号
  if (this.lastTimestamp == timestamp) {
    lastSequence = lastSequence + 1;
    if (lastSequence > 4095L) {
      timestamp = nextMill(lastTimestamp); // 下一毫秒
      lastSequence = 0L;
    }
  } else {
    lastSequence = 0L;
  }

  // 上次生成id的时间戳
  lastTimestamp = timestamp;

  // 时间部分
  long timePart = timestamp - snsEpoch;

  return (timePart << 22) | (DATA_ID << 17) | (WOKER_ID << 12) | lastSequence;
}

/**
 * 获取当前毫秒数
 */
private long timeGen() {
  return System.currentTimeMillis();
}

/**
 * 下一毫秒
 */
private long nextMill(long lastMill) {
  long cur = System.currentTimeMillis();
  while (lastMill <= cur) {
    cur = System.currentTimeMillis();
  }
  return cur;
}

/**
 * 数据中心Id，使用hostname（机器名）取余，值最大为5个bit最大值11111 = 31
 */
private static long dataIdGen() {
  try {
    return getHostId(Inet4Address.getLocalHost().getHostName(), 31);
  } catch (UnknownHostException e) {
    return ThreadLocalRandom.current().nextLong(32);
  }
}

/**
 * 机器Id，使用hostadddress（IP地址）取余，获得的值最大为5个bit最大值11111 = 31
 */
private static long workIdGen() {
  try {
    return getHostId(Inet4Address.getLocalHost().getHostAddress(), 31);
  } catch (UnknownHostException e) {
    return ThreadLocalRandom.current().nextLong(32);
  }
}

/**
 * 对字符串取余，获得的结果最大为max<br>
 * 为了将字符串转成一个Long
 */
private static long getHostId(String value, int max) {
  byte[] bytes = value.getBytes();
  int sum = 0;
  for (byte b : bytes) {
    sum += b;
  }
  return sum % (max + 1);
}

В конце концов, здесь есть некоторые операции сдвига, потому что мы генерируем4Каждый ключLongтип т.е.64немного, нужно перейти в соответствующую позицию. После перемещения вакансия будет заполнена нулями, а затем будет выполнена операция ИЛИ, так что значение исходного ключа не изменится, и, наконец, оно будет преобразовано вLongМы получаем уникальный идентификатор, который нам нужен. Однако эта реализация все же отличается от онлайновой, фактически для оптимизации производительности добавлены некоторые битовые операции, разницы по сути нет.

основы битовых операций

Для удобства описания выражаю его в виде таблицы:

символ	название	Введение	Пример
&	а также	Пока один равен 0, он равен 0	101&001=001
|	или	Пока один равен 1, он равен 1	101|001=101
^	исключающее ИЛИ	Только 1 и 0 будет 1	101^001=100
~	отрицать	Отрицательный, бит 1 становится 0, 0 становится 1	~101=010

Реализация финальной версии

Вот версия непосредственно для справки.

import java.net.Inet4Address;
import java.net.UnknownHostException;
import java.util.Random;

public class SnowflakeUtils {

 /** 时间部分所占长度 */
 private static final int TIME_LEN = 41;
 /** 数据中心id所占长度 */
 private static final int DATA_LEN = 5;
 /** 机器id所占长度 */
 private static final int WORK_LEN = 5;
 /** 毫秒内序列所占长度 */
 private static final int SEQ_LEN = 12;

 /** 定义起始时间 2015-01-01 00:00:00 */
 private static final long START_TIME = 1420041600000L;
 /** 上次生成ID的时间截 */
 private static long LAST_TIME_STAMP = -1L;
 /** 时间部分向左移动的位数 22 */
 private static final int TIME_LEFT_BIT = 64 - 1 - TIME_LEN;

 /** 自动获取数据中心id（可以手动定义 0-31之间的数） */
 private static final long DATA_ID = getDataId();
 /** 自动机器id（可以手动定义 0-31之间的数） */
 private static final long WORK_ID = getWorkId();
 /** 数据中心id最大值 31 */
 private static final int DATA_MAX_NUM = ~(-1 << DATA_LEN);
 /** 机器id最大值 31 */
 private static final int WORK_MAX_NUM = ~(-1 << WORK_LEN);
 /** 随机获取数据中心id的参数 32 */
 private static final int DATA_RANDOM = DATA_MAX_NUM + 1;
 /** 随机获取机器id的参数 32 */
 private static final int WORK_RANDOM = WORK_MAX_NUM + 1;
 /** 数据中心id左移位数 17 */
 private static final int DATA_LEFT_BIT = TIME_LEFT_BIT - DATA_LEN;
 /** 机器id左移位数 12 */
 private static final int WORK_LEFT_BIT = DATA_LEFT_BIT - WORK_LEN;

 /** 上一次的毫秒内序列值 */
 private static long LAST_SEQ = 0L;
 /** 毫秒内序列的最大值 4095 */
 private static final long SEQ_MAX_NUM = ~(-1 << SEQ_LEN);

 public synchronized static long genId() {
  long now = System.currentTimeMillis();

  // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
  if (now < LAST_TIME_STAMP) {
   throw new RuntimeException(String.format(
     "Clock moved backwards.  Refusing to generate id for %d milliseconds", LAST_TIME_STAMP - now));
  }

  if (now == LAST_TIME_STAMP) {
   LAST_SEQ = (LAST_SEQ + 1) & SEQ_MAX_NUM;
   if (LAST_SEQ == 0) {
    now = nextMillis(LAST_TIME_STAMP);
   }
  } else {
   LAST_SEQ = 0;
  }

  // 上次生成ID的时间截
  LAST_TIME_STAMP = now;

  return ((now - START_TIME) << TIME_LEFT_BIT) | (DATA_ID << DATA_LEFT_BIT) | (WORK_ID << WORK_LEFT_BIT)
    | LAST_SEQ;
 }

 /**
  * 获取下一不同毫秒的时间戳，不能与最后的时间戳一样
  */
 public static long nextMillis(long lastMillis) {
  long now = System.currentTimeMillis();
  while (now <= lastMillis) {
   now = System.currentTimeMillis();
  }
  return now;
 }

 /**
  * 获取字符串s的字节数组，然后将数组的元素相加，对（max+1）取余
  */
 private static int getHostId(String s, int max) {
  byte[] bytes = s.getBytes();
  int sums = 0;
  for (int b : bytes) {
   sums += b;
  }
  return sums % (max + 1);
 }

 /**
  * 根据 host address 取余，发生异常就获取 0到31之间的随机数
  */
 public static int getWorkId() {
  try {
   return getHostId(Inet4Address.getLocalHost().getHostAddress(), WORK_MAX_NUM);
  } catch (UnknownHostException e) {
   return new Random().nextInt(WORK_RANDOM);
  }
 }

 /**
  * 根据 host name 取余，发生异常就获取 0到31之间的随机数
  */
 public static int getDataId() {
  try {
   return getHostId(Inet4Address.getLocalHost().getHostName(), DATA_MAX_NUM);
  } catch (UnknownHostException e) {
   return new Random().nextInt(DATA_RANDOM);
  }
 }

}

Подтаблица с несколькими ключами

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

фон проблемы

Мы знаем, что в платежных системах, если используется только одно полеorderIdНедостаточно сделать заказ. Поскольку заказ на предоплату будет создан при вызове платежа на терминале.Вообще говоря, пользователь бизнес-заказа может инициировать несколько платежных операций кассира (подумайте о том, чтобы нажать кнопку оплаты, когда вы рубите руку, вводите пароль, а затем выходите Спустя два часа я все еще не мог сдержать радость от покупки). Если платежная система полагается на то, что этот бизнес-порядок является идемпотентным, это, очевидно, противоречит бизнесу. Итак, в общем случае будет другое идемпотентное полеbus_unique_id. Что ж, приведенное выше введение пригодится, это поле обычно генерируется генератором чисел. Каждый раз, когда вы звоните кассиру, чтобы попросить платежную систему пройти в одном и том жеorderIdи разныеbus_unique_idВот так, идеально.

Проблема возникает в платежной системе.Вообще говоря, наш платежный расходомер делится по определенным правилам. Если это так, то правило подтаблицы должно быть таким же, какbus_unique_idСуществует связь, потому что бизнес должен запрашивать поток платежей через это поле. В нашей платежной системе также будет серийный номер платформы.serial_noПонятие , создано нашим внутренним использованием эмитента, и это поле деятельности также будет использоваться в качестве уникального идентификатора для запроса результатов проточной воды. такbus_unique_idа такжеserial_noОн должен быть помещен в таблицу по определенному алгоритму, потому что интерфейс запроса должен иметь возможность передавать эти два поля, у нас нет возможности проверить две таблицы внутри и, наконец, объединить результаты и вернуть их бизнесу, который это слишком глупо.

заказной сигнальщик

Хорошо, в этой статье не обсуждается реализация подтаблиц, а только алгоритм.

Предположим, у нас есть16подтаблица Чжан,p_mer_pay_${0..15}В общем, бери по модулю16можно направить на стол.bus_unique_idИспользуя это правило, и это поле передается бизнесом, мы не можем его контролировать и, как правило, не работаем повторно для изменения исходных данных. Итак, проблема превращается вserial_noКак действует правило генерацииbus_unique_idпроисходит ассоциация.

Здесь моя реализация выглядит так:

//先使用发号器生成唯一ID
Long preID = UniqueIDProvider.getUniqueID();
//然后清空低7位
preID = (preID >> 7) << 7;
//hash 算法一定程度保证传入bus_unique_id的均匀。
long hashcode = hash(bus_unique_id);
//57位拼上hash后的低7位
long orderid = preID | (hashcode & 127);

public static long hash(Long key) {
    byte[] keys = String.valueof(key).getBytes(Charset.forName("utf-8"));
    int hashcode = new HashCodeBuilder().append(keys).toHashCode();
    return hashcode & 0x7FFFFFFF;
}

Среди них, в алгоритме хеширования,16база0x7FFFFFFFНа самом деле этоInteger.MAX_VALUE, преобразуется в двоичный вид как0000000000000000000000000000000001111111111111111111111111111111.

127Преобразовать в двоичный для низкого7бит..00001111111, высокое положение0. так что используйтеhashcode & 127назад有0即0, в итоге только после7Значение бита зарезервировано, и все предыдущие старшие биты становятся0.

а такжеpreIDпосле7биты0, так что операция ИЛИ有1即1, не влияетpreIDвперед57битовое значение, за которым следует0Просто не влияя на значение в правой части операции. Это делает это64Новое значение бита.

Некоторые друзья могут спросить, почему операция должна быть низкой7кусочек? Почему этоbus_unique_idКлюч падает на стол?

Хороший вопрос, вы действительно любопытный ребенок, давайте сначала посмотрим на черную технологию:

На самом деле результат десятичного числа M % N зависит от значения logN после преобразования числа M в двоичное.

Возьмите каштан:

Integer count = 0;
for (;;) {
  long currentTimeMillis = System.currentTimeMillis();
  if (currentTimeMillis % 16 == 0) {
    System.out.println(toBinaryString(currentTimeMillis));
    count++;
  }
  if (count == 10) {
    break;
  }
}
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000
//  0000000000000000000000010111001011110101011011001100011101110000

log16ценность4, вы можете внимательно наблюдать, что их низкий4немного не все0000, Если вы мне не верите, вы можете сами провести эксперимент и попробовать его с другими числами. Вывод состоит в том, что результаты по модулю одинаковы, их низкиеlogNБит такой же. Вот результат0например, поэтому младшие биты0,Можешь попробоватьcurrentTimeMillis % 16 == 1Ситуация, хотя низкий уровень другой, вывод тот же.

Тогда вы думаете,serial_noа такжеbus_unique_idнизкий7Что значит бит тот же? Это не значит, что они2^7Будете ли вы получать такое же значение, когда Другими словами, наши правила подтаблицы поддерживают максимум128лист. Но мы не модели16? это сейчас низко7Биты одинаковые, низкие4Разве биты не одинаковы? Что значит то же самое? Это не значит, что это2^4=16Это тот же остаток?

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

послесловие

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