Hash - таблица

@nexen · Регистрация: 27.01.2012

Author24 — интернет-сервис помощи студентам

Собственно всегда считал, что map - обычная хеш-таблица, оказалось нет, это какое-то древовидная упорядоченная хэш-таблица (без понятия, как это, но в общем сложность O(logN) на вставку, удаление и поиск.
Для моей задачи было бы предпочтительнее использовать обычную хеш-таблицу со сложностью O(1).
Вопрос: есть ли она (хеш-таблица с O(1) ) в STL и что за "древовидная упорядоченная" map?
~~Пожалуйста, не говорите, что ручками написать несложно хеш-таблицу обычную >_<~~

MrGluck · 21.06.2013, 20:50

@nexen, она реализована на К.Ч. деревьях - бинарные деревья с автобалансировкой. Можете почитать про них на досуге где-нибудь.

hash

Добавлено через 2 минуты
std::unordered_set на ней основан, поиск в среднем за O(1)

@nexen · 22.06.2013, 07:31 **[ТС]**

@MrGluck, но та ссылка, что вы дали, рассказывает о функции, что считает хэш, а не о контейнере, который позволяет по ключу (хешу) получить элемент/ы

MrGluck · 22.06.2013, 18:31

@nexen, std::hash_set и std::hash_map но это из С++11

@nexen · 22.06.2013, 18:49 **[ТС]**

@MrGluck, то есть в 3-ке нету хеш-таблиц? :0 Вообще?

MrGluck · 22.06.2013, 19:04

@nexen, нет. Буст вам в помощь boost/functional/hash.hpp, boost/unordered_set.hpp, насчет hash_set не знаю.

Убежденный · 22.06.2013, 19:13

Сообщение от nexen

то есть в 3-ке нету хеш-таблиц?

По стандарту - нет. Но в некоторых реализациях хэш-таблицы все же есть.
Например, в Microsoft C++ Compiler им уже лет десять от роду, не меньше.
Правда, они не стандартны, так что переносимость не гарантируется.

@nexen · 22.06.2013, 19:17 **[ТС]**

@Убежденный, @MrGluck, а у boost разве переносимость гарантируется?

Убежденный · 22.06.2013, 19:20

Сообщение от nexen

а у boost разве переносимость гарантируется?

Еще как !
Взято отсюда: http://www.boost.org/users/his... _53_0.html

Compilers Tested

Boost's primary test compilers are:
Linux:

GCC: 4.1.2, 4.2.4, 4.4.4, 4.5.3, 4.6.3, 4.7.2

GCC, C++11 mode: 4.4.4, 4.5.3, 4.6.3, 4.7.2

Intel: 11.1, 12.1

LLVM Clang: 2.8

LLVM Clang, with libc++: 3.2
OS X:

GCC: 4.4.7

GCC, C++11 mode: 4.4.4

Intel: 11.1, 12.0
Windows:

Visual C++: 9.0, 10.0
FreeBSD:

GCC: 4.2.1, 32 and 64 bit

Boost's additional test compilers include:
Linux:

Cray: 4.6.1

Clang: from subversion

LLVM Clang, with libc++: 3.2

GCC: 4.2.4, 4.4.4, 4.5.3, 4.6.3, 4.7.1

GCC, C++11 mode: 4.4.4, 4.5.3, 4.6.3, 4.7.1, 4.7.2

pgCC: 11.9

Intel: 10.1, 11.1, 12.1

Intel, C++11 mode: 13.0.1

Visual Age:
OS X:

Clang: from subversion

Clang, C++11 mode: from subversion

Intel: 11.1, 12.0

GCC: 4.4.7

GCC, C++11 mode: 4.4.4
Windows:

Visual C++: 10.0, 11.0

Visual C++ with STLport: 9.0

Visual C++, Windows Mobile 5, with STLport: 9.0
AIX:

IBM XL C/C++ Enterprise Edition: V12.1.0.1

MrGluck · 22.06.2013, 19:35

@nexen, а как вы думаете, какая переносимость у кроссплатформенной библиотеки?

@nexen · 22.06.2013, 20:52 **[ТС]**

@MrGluck, ну мало ли что..

Jupiter · 22.06.2013, 21:13

Сообщение от nexen

ну мало ли что..

что?

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
		1
	Hash - таблица 21.06.2013, 20:46. Показов 1388. Ответов 11 Метки нет (Все метки) Собственно всегда считал, что map - обычная хеш-таблица, оказалось нет, это какое-то древовидная упорядоченная хэш-таблица (без понятия, как это, но в общем сложность O(logN) на вставку, удаление и поиск. Для моей задачи было бы предпочтительнее использовать обычную хеш-таблицу со сложностью O(1). Вопрос: есть ли она (хеш-таблица с O(1) ) в STL и что за "древовидная упорядоченная" map? ~~Пожалуйста, не говорите, что ручками написать несложно хеш-таблицу обычную >_<~~ 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	21.06.2013, 20:50	2
	@nexen, она реализована на К.Ч. деревьях - бинарные деревья с автобалансировкой. Можете почитать про них на досуге где-нибудь. hash Добавлено через 2 минуты std::unordered_set на ней основан, поиск в среднем за O(1) 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	22.06.2013, 07:31 [ТС]	3
	@MrGluck, но та ссылка, что вы дали, рассказывает о функции, что считает хэш, а не о контейнере, который позволяет по ключу (хешу) получить элемент/ы 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	22.06.2013, 18:31	4
	@nexen, std::hash_set и std::hash_map но это из С++11 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	22.06.2013, 18:49 [ТС]	5
	@MrGluck, то есть в 3-ке нету хеш-таблиц? :0 Вообще? 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	22.06.2013, 19:04	6
	@nexen, нет. Буст вам в помощь boost/functional/hash.hpp, boost/unordered_set.hpp, насчет hash_set не знаю. 1

Убежденный Ушел с форума 16473 / 7436 / 1187 Регистрация: 02.05.2013 Сообщений: 11,617 Записей в блоге: 1
	22.06.2013, 19:13	7
	Сообщение от nexen то есть в 3-ке нету хеш-таблиц? По стандарту - нет. Но в некоторых реализациях хэш-таблицы все же есть. Например, в Microsoft C++ Compiler им уже лет десять от роду, не меньше. Правда, они не стандартны, так что переносимость не гарантируется. 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	22.06.2013, 19:17 [ТС]	8
	@Убежденный, @MrGluck, а у boost разве переносимость гарантируется? 0

Убежденный Ушел с форума 16473 / 7436 / 1187 Регистрация: 02.05.2013 Сообщений: 11,617 Записей в блоге: 1
	22.06.2013, 19:20	9
	Сообщение от nexen а у boost разве переносимость гарантируется? Еще как ! Взято отсюда: http://www.boost.org/users/his... _53_0.html Compilers Tested Boost's primary test compilers are: Linux: GCC: 4.1.2, 4.2.4, 4.4.4, 4.5.3, 4.6.3, 4.7.2 GCC, C++11 mode: 4.4.4, 4.5.3, 4.6.3, 4.7.2 Intel: 11.1, 12.1 LLVM Clang: 2.8 LLVM Clang, with libc++: 3.2 OS X: GCC: 4.4.7 GCC, C++11 mode: 4.4.4 Intel: 11.1, 12.0 Windows: Visual C++: 9.0, 10.0 FreeBSD: GCC: 4.2.1, 32 and 64 bit Boost's additional test compilers include: Linux: Cray: 4.6.1 Clang: from subversion LLVM Clang, with libc++: 3.2 GCC: 4.2.4, 4.4.4, 4.5.3, 4.6.3, 4.7.1 GCC, C++11 mode: 4.4.4, 4.5.3, 4.6.3, 4.7.1, 4.7.2 pgCC: 11.9 Intel: 10.1, 11.1, 12.1 Intel, C++11 mode: 13.0.1 Visual Age: OS X: Clang: from subversion Clang, C++11 mode: from subversion Intel: 11.1, 12.0 GCC: 4.4.7 GCC, C++11 mode: 4.4.4 Windows: Visual C++: 10.0, 11.0 Visual C++ with STLport: 9.0 Visual C++, Windows Mobile 5, with STLport: 9.0 AIX: IBM XL C/C++ Enterprise Edition: V12.1.0.1 1

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	22.06.2013, 19:35	10
	@nexen, а как вы думаете, какая переносимость у кроссплатформенной библиотеки? 1

	22.06.2013, 21:13

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	22.06.2013, 20:52 [ТС]	11
	@MrGluck, ну мало ли что.. 0

Jupiter Каратель 6609 / 4028 / 401 Регистрация: 26.03.2010 Сообщений: 9,273 Записей в блоге: 1
	22.06.2013, 21:13	12
	Сообщение от nexen ну мало ли что.. что? 0