StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POConverting Static to Dynamic Hash Table
primarykey
Id
16907423
data
AcceptedAnswerId
0
AnswerCount
2
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-06-03T23:23:35.500
FavoriteCount
0
LastActivityDate
2013-06-04T02:20:05.550
LastEditDate
LastEditorUserId
0
OwnerUserId
2217870
ParentId
0
PostTypeId
1
Score
0
ViewCount
440
LastEditorDisplayName
text
Body
<p>I'be been given the assignment to change a given hash-table with static memory allocation to dynamic, so that more memory can be allocated past the limit while the program is running. I by no means am demanding a solution to the problem, I'm simply asking if anyone knows a good place to start or which aspects of the code I need to pay attention to as I'm a little lost and confused with hash tables. I know the enums and the constructor needs to be changed but I'm not sure of much else. Here is the code given, and thanks in advance for any advice:</p> <pre><code>#ifndef TABLE1_H #define TABLE1_H #include <cstdlib> // Provides size_t #include <cassert> // Provides assert namespace main_savitch_12A { template <class RecordType> class table { public: enum { CAPACITY = 30 }; // CONSTRUCTOR table( ); // MODIFICATION MEMBER FUNCTIONS void insert(const RecordType& entry); void remove(int key); // CONSTANT MEMBER FUNCTIONS bool is_present(int key) const; void find(int key, bool& found, RecordType& result) const; size_t size( ) const { return used; } private: // MEMBER CONSTANTS -- These are used in the key field of special records. enum { NEVER_USED = -1 }; enum { PREVIOUSLY_USED = -2 }; // MEMBER VARIABLES RecordType data[CAPACITY]; size_t used; // HELPER FUNCTIONS size_t hash(int key) const; size_t next_index(size_t index) const; void find_index(int key, bool& found, size_t& index) const; bool never_used(size_t index) const; bool is_vacant(size_t index) const; }; template <class RecordType> table<RecordType>::table( ) { size_t i; used = 0; for (i = 0; i < CAPACITY; ++i) data[i].key = NEVER_USED; // Indicates a spot that's never been used. } template <class RecordType> void table<RecordType>::insert(const RecordType& entry) // Library facilities used: cassert { bool already_present; // True if entry.key is already in the table size_t index; // data[index] is location for the new entry assert(entry.key >= 0); // Set index so that data[index] is the spot to place the new entry. find_index(entry.key, already_present, index); // If the key wasn't already there, then find the location for the new entry. if (!already_present) { assert(size( ) < CAPACITY); index = hash(entry.key); while (!is_vacant(index)) index = next_index(index); ++used; } data[index] = entry; size_t i; for (i=0; i<CAPACITY; i++) cout << data[i].key << ' '; cout << endl; } template <class RecordType> void table<RecordType>::remove(int key) // Library facilities used: cassert { bool found; // True if key occurs somewhere in the table size_t index; // Spot where data[index].key == key assert(key >= 0); find_index(key, found, index); if (found) { // The key was found, so remove this record and reduce used by 1. data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use. --used; } } template <class RecordType> bool table<RecordType>::is_present(int key) const // Library facilities used: assert.h { bool found; size_t index; assert(key >= 0); find_index(key, found, index); return found; } template <class RecordType> void table<RecordType>::find(int key, bool& found, RecordType& result) const // Library facilities used: cassert.h { size_t index; assert(key >= 0); find_index(key, found, index); if (found) result = data[index]; } template <class RecordType> inline size_t table<RecordType>::hash(int key) const { return (key % CAPACITY); } template <class RecordType> inline size_t table<RecordType>::next_index(size_t index) const // Library facilities used: cstdlib { return ((index+1) % CAPACITY); } template <class RecordType> void table<RecordType>::find_index(int key, bool& found, size_t& i) const // Library facilities used: cstdlib { size_t count; // Number of entries that have been examined count = 0; i = hash(key); while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key)) { ++count; i = next_index(i); } found = (data[i].key == key); } template <class RecordType> inline bool table<RecordType>::never_used(size_t index) const { return (data[index].key == NEVER_USED); } template <class RecordType> inline bool table<RecordType>::is_vacant(size_t index) const { return (data[index].key == NEVER_USED);// || (data[index].key == PREVIOUSLY_USED); } } #endif </code></pre>
Tags
<c++><hashtable>
Title
Converting Static to Dynamic Hash Table
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USFilT
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
  singulars
  PostTypePostTypeId
  PTAnswer
2. PO
  singulars
  PostTypePostTypeId
  PTAnswer
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.