Быстрый Строковый Алгоритм хеширования с низким уровнем аварийности с [закрытым] целым числом на 32 бита
NullPointerException s - исключения, возникающие при попытке использовать ссылку, которая указывает на отсутствие местоположения в памяти (null), как если бы она ссылалась на объект. Вызов метода по нулевой ссылке или попытка получить доступ к полю нулевой ссылки вызовет функцию NullPointerException. Они наиболее распространены, но другие способы перечислены на странице NullPointerException javadoc.
Вероятно, самый быстрый пример кода, который я мог бы придумать для иллюстрации NullPointerException, be:
public class Example {
public static void main(String[] args) {
Object obj = null;
obj.hashCode();
}
}
В первой строке внутри main я явно устанавливаю ссылку Object obj равной null. Это означает, что у меня есть ссылка, но она не указывает на какой-либо объект. После этого я пытаюсь обработать ссылку так, как если бы она указывала на объект, вызывая метод на нем. Это приводит к NullPointerException, потому что нет кода для выполнения в местоположении, на которое указывает ссылка.
(Это техничность, но я думаю, что она упоминает: ссылка, которая указывает на null, равна 't то же, что и указатель C, указывающий на недопустимую ячейку памяти. Нулевой указатель буквально не указывает на в любом месте , который отличается от указаний на местоположение, которое оказывается недопустимым.)
12 ответов
Один из варианты FNV должен отвечать Вашим требованиям. Они быстры, и производят справедливо равномерно распределенные выводы.
CRC-32. Существует приблизительно триллион ссылок на Google для него.
Существует некоторое хорошее обсуждение в этом предыдущий вопрос
И хороший обзор того, как выбрать хеш-функции, а также статистику о распределении нескольких общих здесь
Вы видите то, что.NET использует на Строке. GetHashCode () метод с помощью Отражателя.
я рисковал бы предположением, что Microsoft провела значительное время, оптимизируя это. Они распечатали во всей документации MSDN также, что она подвержена изменениям все время. Так ясно это находится на их "радаре тонкой настройки производительности";-)
было бы довольно тривиально к порту к C++ также, я буду думать.
у Bob Jenkins есть много хеш-функций, доступных , все из которых быстры и имеют низкий уровень аварийности.
хеш-функция Hsieh довольно хороша, и имеет некоторые сравнительные тесты/сравнения как общая хеш-функция в C. В зависимости от того, что Вы хотите (это не абсолютно очевидно) Вы могли бы хотеть рассмотреть что-то как cdb вместо этого.
Почему Вы только не пользуетесь библиотеки Boost? Их хеш-функция проста в использовании, и большая часть материала в Повышении скоро будет частью стандарта C++. Часть его уже.
хеш Повышения так же легок как
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
, можно найти повышение в boost.org
Другое решение, которое могло быть еще лучше в зависимости от Вашего примера использования, интернированные строки . Это - то, как символы работают, например, в Lisp.
интернированная строка является строковым объектом, значение которого является адресом фактических строковых байтов. Таким образом, Вы создаете интернированный строковый объект путем регистрации в глобальной таблице: если строка там, Вы инициализируете интернированную строку к адресу той строки. В противном случае Вы вставляете его, и затем инициализируете Вашу интернированную строку.
Это означает, что две интернированных строки, созданные из той же строки, будут иметь то же значение, которое является адресом. Таким образом, если N является количеством интернированных строк в Вашей системе, характеристики:
- Медленная конструкция (поиск потребностей и возможно выделение памяти)
- Требует, чтобы глобальные данные и синхронизация в случае параллельных потоков
- Выдержали сравнение, O (1), потому что Вы сравниваете адреса, не фактические строковые байты (это означает сортировать работы хорошо, но это не будет алфавитный вид).
С наилучшими пожеланиями,
Carl
Существует также хорошая статья в eternallyconfuzzled.com .
Jenkins По одному хеширует для строк, должен выглядеть примерно так:
#include <stdint.h>
uint32_t hash_string(const char * s)
{
uint32_t hash = 0;
for(; *s; ++s)
{
hash += *s;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Для фиксированного установленного на строку использования gperf.
, Если Ваши установленные на строку изменения необходимо выбрать одну хеш-функцию. Та тема была обсуждена прежде: