title: C++ Hash Table Seg Fault (Pointer Allocation)
body: <p>I am trying to implement a Hash Table using Linear Probing. However, in my search function, a seg fault is occurring, and I am unsure why. It seems to be to do with how I am initialising the Hash Table within the class definition - I do not think it is liking the <code>table[i] = new HashNode()</code> part, although I know everything is being created due to having couts there previously.</p>
  <p>The Search function is part of my Insert function. I have already checked that my HashFunction function (assigns an index to a word) is working correctly.</p>
  <p>My HashNode class is declared as follows:</p>
  <pre><code>class HashNode{
  public:
  string word ;
  string status ;
  
  // Basic constructor for a node
  HashNode(string word, string status) {
      // this keyword references the key and word variables which belong to the class
      this-&gt;word = word ;
      this-&gt;status = status ;
  }
  } ;
  </code></pre>
  <p>My HashTable class is declared as follows:</p>
  <pre><code>class HashTable{
  private:
  // Contains an array of pointers to items
  HashNode **table ;  // 2D array
  static const int TableSlots = 26 ;  // size of alphabet
  int size ;  // current size
  // Create tombstone node
  HashNode *tombstone ;
  public:
  // Initialise constructor
  HashTable(){
      size = 0 ;
      HashNode **table = new (HashNode*)[TableSlots] ;
  
      // Initialise all elements of array to &quot;never used&quot;, aka. NULL
      for (int i = 0; i &lt; TableSlots; i++){
          // Allocate pointer to a singular node (2nd dimension of 2D array)
          // Only one node as no chaining is required
          table[i] = new HashNode(&quot;NULL&quot;, &quot;never used&quot;) ; // deference pointer
          cout &lt;&lt; &quot;hash node status: &quot; &lt;&lt; table[i]-&gt;status &lt;&lt; endl ;
          cout &lt;&lt; &quot;hash node word: &quot; &lt;&lt; table[i]-&gt;word &lt;&lt; endl ;
      }
  
      // Initialise tombstone node
      tombstone = new HashNode(&quot;NULL&quot;,&quot;tombstone&quot;) ;
  
      cout &lt;&lt; &quot;created hash table&quot; &lt;&lt; endl ;
  }
  // Hashing function: takes a key, returns integer
  int hashFunction(string word) ;
  // Search function (returns true/false)
  bool Search(string word) ;
  // Helper function (provides index)
  int SearchSlot(string word) ;
  // Insert function
  void Insert(string word) ;
  // Delete function
  void deleteNode(string word) ;
  // Print function
  void printNode() ;
  } ;
  </code></pre>
  <p>My hash function:</p>
  <pre><code>// Function assumes the key is valid and not empty
  int HashTable::hashFunction(string word){
  
  cout &lt;&lt; &quot;hash function implemented&quot; &lt;&lt; endl ;
  cout &lt;&lt; &quot;word passed to function: &quot; ;
  for (int i = 0; i &lt; word.size(); i++) cout &lt;&lt; word[i] ;
      cout &lt;&lt; endl ;
  
  char lastChar = word[word.size()-1] ;
  
  // Initialise return variable
  int slot_num ;
  
  // There are 26 different lists (array indexes include 0-25)
  // a-&gt;0, b-&gt;1, etc.
  if (lastChar == 'a') slot_num = 0 ;
  else if (lastChar == 'b') slot_num = 1 ; 
  else if (lastChar == 'c') slot_num = 2 ; 
  else if (lastChar == 'd') slot_num = 3 ; 
  else if (lastChar == 'e') slot_num = 4 ; 
  else if (lastChar == 'f') slot_num = 5 ; 
  else if (lastChar == 'g') slot_num = 6 ; 
  else if (lastChar == 'h') slot_num = 7 ; 
  else if (lastChar == 'i') slot_num = 8 ; 
  else if (lastChar == 'j') slot_num = 9 ; 
  else if (lastChar == 'k') slot_num = 10 ; 
  else if (lastChar == 'l') slot_num = 11 ; 
  else if (lastChar == 'm') slot_num = 12 ; 
  else if (lastChar == 'n') slot_num = 13 ; 
  else if (lastChar == 'o') slot_num = 14 ; 
  else if (lastChar == 'p') slot_num = 15 ; 
  else if (lastChar == 'q') slot_num = 16 ; 
  else if (lastChar == 'r') slot_num = 17 ; 
  else if (lastChar == 's') slot_num = 18 ; 
  else if (lastChar == 't') slot_num = 19 ; 
  else if (lastChar == 'u') slot_num = 20 ; 
  else if (lastChar == 'v') slot_num = 21 ; 
  else if (lastChar == 'w') slot_num = 22 ; 
  else if (lastChar == 'x') slot_num = 23 ; 
  else if (lastChar == 'y') slot_num = 24 ;
  else if (lastChar == 'z') slot_num = 25 ;  
  
  return slot_num % TableSlots ;
  }
  </code></pre>
  <p>My Search function:</p>
  <pre><code>bool HashTable::Search(string word){
  
  cout &lt;&lt; &quot;search function called&quot; &lt;&lt; endl ;
  
  // Get first possible index for given word
  int slot = hashFunction(word) ;
  
  cout &lt;&lt; &quot;table size:&quot; &lt;&lt; table.size() &lt;&lt; endl ;
  //table[slot]-&gt;word = word ;
  cout &lt;&lt; &quot;slot num from search function: &quot; &lt;&lt; slot &lt;&lt; endl ; 
  // SEG FAULTS HERE //
  cout &lt;&lt; &quot;table slot 0&quot; &lt;&lt; table[slot]-&gt;word &lt;&lt; endl ;
  
  cout &lt;&lt; &quot;table slot status&quot; &lt;&lt; table[slot]-&gt;status &lt;&lt; endl ;
  
  /*
  Each letter has its own key, but:
      a) may have multiple words which end with the same letter
      b) word may have moved index due to collision
      c) word may be placed after a &quot;tombstone&quot; slot
  */
  while (table[slot]-&gt;status != &quot;never used&quot;){
      // if the node is found, return true
      //if ( strcmp(table[slot]-&gt;word, word) ) return true ;
      if(table[slot]-&gt;word == word) return true ;
      // increment index and wrap back around the table
      slot++ ;
      slot %= TableSlots ;
  }
  
  cout &lt;&lt; &quot;word not found, returning false&quot; &lt;&lt; endl ;
  
  return false ;
  }
  </code></pre>
  <p>My Insert function:</p>
  <pre><code>void HashTable::Insert(string word){
  
  // Search to see if the node exists
  bool exists = Search(word) ;
  cout &lt;&lt; &quot;exists: &quot; &lt;&lt; exists &lt;&lt; endl ;
  
  if (exists == false){
      // Create a new node
      //HashNode *temp = new HashNode(word, &quot;occupied&quot;) ;
  
      cout &lt;&lt; &quot;inserting&quot; &lt;&lt; endl ;
  
      int slot = hashFunction(word) ;
  
      while (table[slot]-&gt;status != &quot;never used&quot; &amp;&amp; table[slot]- 
  &gt;status != &quot;tombstone&quot;)
      {
          slot++ ;
          slot %= TableSlots ;
      }
  
      table[slot]-&gt;word = word ;
      table[slot]-&gt;status = &quot;occupied&quot; ;  // sets status to 
      // occupied by default
      size++ ;    // increase current size of occupied slots in 
      // hash table
  }
  }
  </code></pre>
  <p>My delete function:</p>
  <pre><code>void HashTable::deleteNode(string word){
  
  // Search to see if the node exists
  bool exists = Search(word) ;
  
  if (exists == true){
      int slot = SearchSlot(word) ;   // get index of slot
  
      // Get temp pointer
      HashNode *temp = table[slot] ;
  
      // Set table slot to tombstone hashnode
      table[slot] = tombstone ;
  
      // Delete temp node
      delete(temp) ;
  
      // Decrement current size of occupied hash table slots
      size-- ;
  }
  
  }
  </code></pre>
  <p>My main function:</p>
  <pre><code>int main(){
  
  string input ;
  getline(cin, input) ;
  
  size_t start = 0 ;
  size_t space = input.find_first_of(&quot; &quot;) ;
  string func ;   // to store first characters in, no bigger than 26
  vector&lt;string&gt; filtered ;   // to store each word or 'key' in
  unsigned int len = 0 ;  // substring length for filtered elements
  
  while(space != string::npos){
  
      // If space &gt; start, a word has been filtered - store as string element
      if (start == 0){
          len = space - start - 1 ;
          filtered.push_back(input.substr(start + 1, len)) ;
          func += input[start] ;
      }
      else if (start != 0){
          len = space - start - 2 ;
          filtered.push_back(input.substr(start + 2, len)) ;
          func += input[start + 1] ;
      }
  
      start = space++ ;
      space = input.find_first_of(&quot; &quot;, space) ;
  }
  
  // Add last word (cut off during while loop once string::npos is 
  // reached)
  func+= input[start + 1] ;
  filtered.push_back(input.substr(start + 2)) ;
  
  for (int i = 0; i &lt; filtered.size(); i++) cout &lt;&lt; filtered[i] &lt;&lt; 
  &quot; &quot; ;
      cout &lt;&lt; endl ;
  
  // Instantiate a new HashTable object
  HashTable *hashT = new HashTable() ;
  
  // Perform insertion/deletion
  for (int i = 0; i &lt; func.size(); i++){
      if (func[i] == 'A') hashT-&gt;Insert(filtered.at(i)) ;
      else if (func[i] == 'D') hashT-&gt;deleteNode(filtered.at(i)) ;
  }
  
  hashT-&gt;printNode() ;
  
  return 0 ;
  }
  </code></pre>
  <p>Apologies for all the couts, just trying to debug the code. I'm also relatively new to C++ so this is for learning and experimentation. Any other comments are welcome.</p>