Check the documentation for DownValues, Set, and Unset. For things that are free of explicit patterns, something like

myTable[key1] = val1;
myTable[key2] = val2;

is effectively a hash table with key and key2 as keys, etc. (and they really are hashed, under the hood). To remove one of these use Unset; I show the infix version below.

myTable[key1] = val1;                                                   
myTable[key2] = val2;               

We look up key:

In[9]:= myTable[key1]                                                           

Out[9]= val1

Now clear it and try that lookup. It will fail to find a value.

In[10]:=  myTable[key1] =.                                                      

In[11]:= myTable[key1]                                                          

Out[11]= myTable[key1]

You are correct on all counts.

Version 10 has Association which provides a means to get Keys and Values separately, amongst numerous other features. It too has a hash table under the hood. One caveat is it might not be as useful if one plans to build it up or modify in many steps.