A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/db/d71/quadratic__probing__hash__table_8cpp_source.html below:

TheAlgorithms/C++: hashing/quadratic_probing_hash_table.cpp Source File

Go to the documentation of this file. 29

std::vector<Entry> table;

57 int

hash =

static_cast<int>

(

hashFxn

(key));

62

(hash +

static_cast<size_t>

(std::round(std::pow(i, 2)))) %

66 if

(entry.

key

== notPresent) {

70

std::cout <<

"Found key!"

<< std::endl;

73

std::cout <<

"Found tombstone or equal hash, checking next" 79

std::cout <<

"Spot found!"

<< std::endl;

84

std::cout <<

"Spot taken, looking at next (next index = " 85

<< (hash +

static_cast<size_t>

(

86

std::round(std::pow(i + 1, 2)))) %

92 if

(i == totalSize * 100) {

93

std::cout <<

"Quadratic probe failed (infinite loop)"

<< std::endl;

96

}

while

(entry.

key

!= notPresent);

107 if

(entry.

key

== notPresent || entry.

key

== tomb) {

120 if

(entry.

key

== key) {

133 if

(index == notPresent) {

143 for

(

int

i = 0; i < totalSize; i++) {

144 if

(table[i].key == notPresent) {

145

std::cout <<

" Empty "

;

146

}

else if

(table[i].key == tomb) {

147

std::cout <<

" Tomb "

;

150

std::cout << table[i].key;

154

std::cout << std::endl;

163 int

oldSize = totalSize;

164

std::vector<Entry> oldTable(table);

167

table = std::vector<Entry>(totalSize);

168 for

(

int

i = 0; i < oldSize; i++) {

169 if

(oldTable[i].key != -1 && oldTable[i].key != notPresent) {

171 add

(oldTable[i].key);

176

std::cout <<

"Table was rehashed, new size is: "

<< totalSize << std::endl;

184

table[index].key = key;

186 if

(++size /

static_cast<double>

(totalSize) >= 0.5) {

196 if

(index == notPresent) {

197

std::cout <<

"key not found"

<< std::endl;

199

table[index].key = tomb;

200

std::cout <<

"Removal successful, leaving tombstone"

<< std::endl;

208

std::cout <<

"Initial table: "

;

210

std::cout << std::endl;

211

std::cout <<

"hash of "

<< key <<

" is "

<<

hashFxn

(key) <<

" % " 212

<< totalSize <<

" == "

<<

hashFxn

(key) % totalSize;

213

std::cout << std::endl;

215

std::cout <<

"New table: "

;

223

std::cout <<

"Initial table: "

;

225

std::cout << std::endl;

226

std::cout <<

"hash of "

<< key <<

" is "

<<

hashFxn

(key) <<

" % " 227

<< totalSize <<

" == "

<<

hashFxn

(key) % totalSize;

228

std::cout << std::endl;

230

std::cout <<

"New table: "

;

240using

quadratic_probing::table;

241using

quadratic_probing::totalSize;

247 int

cmd = 0, key = 0;

248

std::cout <<

"Enter the initial size of Hash Table. = "

;

249

std::cin >> totalSize;

250

table = std::vector<Entry>(totalSize);

253

std::cout << std::endl;

254

std::cout <<

"PLEASE CHOOSE -"

<< std::endl;

255

std::cout <<

"1. Add key. (Numeric only)"

<< std::endl;

256

std::cout <<

"2. Remove key."

<< std::endl;

257

std::cout <<

"3. Find key."

<< std::endl;

258

std::cout <<

"4. Generate Hash. (Numeric only)"

<< std::endl;

259

std::cout <<

"5. Display Hash table."

<< std::endl;

260

std::cout <<

"6. Exit."

<< std::endl;

264

std::cout <<

"Enter key to add = "

;

269

std::cout <<

"Enter key to remove = "

;

274

std::cout <<

"Enter key to search = "

;

279 if

(entry.

key

== quadratic_probing::notPresent) {

280

std::cout <<

"Key not present"

;

285

std::cout <<

"Enter element to generate hash = "

;

287

std::cout <<

"Hash of "

<< key

298

std::cout << std::endl;

An implementation of hash table using quadratic probing algorithm.

void removalInfo(int key)

int quadraticProbe(int key, bool searching)

bool putProber(const Entry &entry, int key)

bool searchingProber(const Entry &entry, int key)

Entry(int key=notPresent)

constructor

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4