Last active
July 19, 2018 16:48
-
-
Save serge-medvedev/736d5e2b4cd5f3f2b121b05167eac18c to your computer and use it in GitHub Desktop.
Hashtable
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Open addressing, linear probing. | |
| */ | |
| template < typename Key, typename Value, class Hash > | |
| class hashtable | |
| { | |
| public: | |
| using capacity_t = uint64_t; | |
| using item_t = struct item | |
| { | |
| Key _key; | |
| Value _value; | |
| item( Key key, Value value ) | |
| : _key( key ) | |
| , _value( value ) | |
| { | |
| } | |
| }; | |
| private: | |
| const capacity_t _capacity; | |
| size_t _size; | |
| const item_t * const _dummy; | |
| item_t ** _data; | |
| public: | |
| hashtable( capacity_t capacity ) | |
| : _capacity( capacity ) | |
| , _size( 0 ) | |
| , _dummy( reinterpret_cast< item_t * >( 0xdeadd00d ) ) | |
| { | |
| _data = new item_t * [ _capacity ]; | |
| for ( auto i = 0; i < _capacity; i++ ) | |
| { | |
| _data[ i ] = nullptr; | |
| } | |
| } | |
| ~hashtable() | |
| { | |
| for ( auto i = 0; i < _capacity; i++ ) | |
| { | |
| if ( _data[ i ] != nullptr && _data[ i ] != _dummy ) | |
| { | |
| delete _data[ i ]; | |
| } | |
| } | |
| delete [] _data; | |
| } | |
| void insert( Key key, Value value ) | |
| { | |
| if ( _size == _capacity ) | |
| { | |
| throw std::runtime_error( "max size is reached" ); | |
| } | |
| auto hasher = Hash(); | |
| auto hash = hasher( key ); | |
| auto index = hash % _capacity; | |
| while ( _data[ index ] != nullptr && _data[ index ] != _dummy && _data[ index ]->_key != key ) | |
| { | |
| index = ( index + 1 ) % _capacity; | |
| } | |
| if ( _data[ index ] != nullptr && _data[ index ] != _dummy && _data[ index ]->_key == key ) | |
| { | |
| _data[ index ]->_value = value; | |
| } | |
| else | |
| { | |
| _data[ index ] = new item_t( key, value ); | |
| _size++; | |
| } | |
| } | |
| Value get( Key key ) const | |
| { | |
| auto hasher = Hash(); | |
| auto hash = hasher( key ); | |
| auto index = hash % _capacity, i = index; | |
| while ( _data[ index ] != nullptr ) | |
| { | |
| if ( _data[ index ] != _dummy && _data[ index ]->_key == key ) | |
| { | |
| return _data[ index ]->_value; | |
| } | |
| index = ( index + 1 ) % _capacity; | |
| if ( index == i ) | |
| { | |
| break; | |
| } | |
| } | |
| throw std::runtime_error( "no such key" ); | |
| } | |
| Value remove( Key key ) | |
| { | |
| auto hasher = Hash(); | |
| auto hash = hasher( key ); | |
| auto index = hash % _capacity, i = index; | |
| while ( _data[ index ] != nullptr ) | |
| { | |
| if ( _data[ index ] != _dummy && _data[ index ]->_key == key ) | |
| { | |
| auto value = _data[ index ]->_value; | |
| delete _data[ index ]; | |
| _data[ index ] = _dummy; | |
| _size--; | |
| return value; | |
| } | |
| index = ( index + 1 ) % _capacity; | |
| if ( index == i ) | |
| { | |
| break; | |
| } | |
| } | |
| throw std::runtime_error( "no such key" ); | |
| } | |
| size_t size() const | |
| { | |
| return _size; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment