Статьи

Как создать уникальное 64-битное целое число из строки

Декабрь 22, 2018

PHP предоставляет популярную хеш-функцию md5 () , которая возвращает 32 шестнадцатеричную строку символов. Это отличный способ создать отпечаток для любой строки произвольной длины. Но что, если вам нужно сгенерировать целое число из URL?

Вызов

Мы столкнулись с этой проблемой в RatingWidget, когда нам пришлось привязать наши рейтинговые виджеты к уникальным идентификаторам Int64 на основе страницы сайта, с которой они загружаются. Теоретически мы могли бы просто хранить URL-адреса и запрашивать столбец URL, но URL-адреса могут быть очень длинными, и создание индекса для текстового столбца с неизвестной длиной очень неэффективно.

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

Чтобы упростить проблему, давайте разделим ее на две подзадачи:

  1. Канонизация URL
  2. Строка в уникальное преобразование Int64

Канонизация URL

В нашем случае мы хотели назначить уникальный Int64 для страницы, а не для URL. Например, http://domain.com?x=1&y=2http://domain.com?y=2&x=1 Поэтому мы хотели присвоить им идентичный Int64 ID. Таким образом, канонизируя URL-адреса перед их отображением в Int64, мы можем преобразовать URL-адреса в единообразное представление. 

 function canonizeUrl($url)
    {
        $url = parse_url(strtolower($url));
        
        $canonic = $url['host'] . $url['path'];
        
        if (isset($url['query']))
        {
            parse_str($url['query'], $queryString);
            $canonic .= '?' . canonizeQueryString($queryString);
        }
        
        return $canonic;
    }
    
    function canonizeQueryString(array $params)
    {
        if (!is_array($params) || 0 === count($params))
            return '';

        // Urlencode both keys and values.
        $keys = urlencode_rfc3986(array_keys($params));
        $values = urlencode_rfc3986(array_values($params));
        $params = array_combine($keys, $values);
    
        // Parameters are sorted by name, using lexicographical byte value ordering.
        // Ref: Spec: 9.1.1 (1)
        uksort($params, 'strcmp');
    
        $pairs = array();
        foreach ($params as $parameter => $value) 
        {
            $lower_param = strtolower($parameter);
            
            if (is_array($value)) 
            {
                // If two or more parameters share the same name, they are sorted by their value
                // Ref: Spec: 9.1.1 (1)
                natsort($value);
                foreach ($value as $duplicate_value)
                    $pairs[] = $lower_param . '=' . $duplicate_value;
            } 
            else 
            {
                $pairs[] = $lower_param . '=' . $value;
            }
        }            
        
        if (0 === count($pairs))
            return '';
    
        return implode('&', $pairs);
    }

    function urlencode_rfc3986($input) 
    {
        if (is_array($input))
            return array_map(array(&$this, 'urlencode_rfc3986'), $input);
        else if (is_scalar($input)) 
            return str_replace('+', ' ', str_replace('%7E', '~', rawurlencode($input)));
            
        return '';
    }

По сути, этот код переупорядочивает параметры строки запроса по лексикографическому порядку и слегка подправляет кодировку URL на основе стандарта синтаксиса URI RFC 3986 , чтобы компенсировать несоответствие кодировки URL различных браузеров + сервера.

Примечания:

  1. В нашем случае canonizeUrl, функция канонизации, избавляется от протокола. Так что https://domain.comhttp://domain.comdomain.com
  2. Как вы можете заметить, мы также игнорируем все после фрагмента хешмарка. Поэтому, если вы хотите создать уникальные идентификаторы для SPA ( одностраничного приложения ) различных состояний, таких как http://my-spa.com/#state1http://my-spa.com/#state2

Преобразование строки в уникальный идентификатор Int64 для индексированного столбца MySql BIGINT

После дурачения с различными функциями преобразования битов, такими как bindec()decbin()base_convert() Мы обнаружили, что 64-битные целые числа и PHP не очень хорошо играют. Ни одна из упомянутых функций последовательно не поддерживает 64-битные Покопавшись в Google, мы получили сообщение о 32-битных ограничениях в PHP, которое включало в себя предложение использовать GMP , действительно классную библиотеку для целых чисел с множественной точностью. Используя эту библиотеку, нам удалось создать эту однострочную хеш-функцию, которая генерирует 64-битное целое число из строки произвольной длины. 

 function get64BitHash($str)
    {
        return gmp_strval(gmp_init(substr(md5($str), 0, 16), 16), 10);
    }

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

Чтобы узнать больше о GMP, смотрите здесь .

Супер финал

Сочетая канонизацию URL с отображением String на Int64, окончательное решение выглядит следующим образом: 

 function urlTo64BitHash($url)
    {
        return get64BitHash(canonizeUrl($url));
    }

Тест столкновения и производительности get64BitHash

Платформа: Intel i3, Windows 7 64 бит, PHP 5.3
Итерации: 10 000 000 раз сгенерировано get64BitHash
Истекшее время: 460 миллисекунд на каждые 100 000 поколений
Столкновение: не найдено

Резюме

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

51
Share: