Please be careful with long lines; they fall off the edge of the screen. I had to add a newline to avoid left-and-right scrolling.
TreeMap implements the Map interface and the Map interface has a method which puts all the Entries into a Set and you can change a Set to an array . . .
Do you need a TreeMap? Is the sorting necessary to your application? If not, can you use a HashMap instead?
JTables are usually discussed in the Swing forum, so I shall have to move you there.
If I use HashMap how will this change things? Please explain...
It won't change things are far as your problem is concerned. The reason Campbell mentioned a HashMap is it is more efficient than a TreeMap (particularly for large data sets) and so unless ordering is important it is better to use a HashMap. The get, put, containsKey type methods run in constant time in a HashMap and log(n) time in a TreeMap.
In your case, unless performance becomes a real issue, I'd use a TreeMap because as you say displaying sorted data looks better than displaying random entries.
Campbell has outlined one way. Another is to create a 2D array where one dimension is 2 and the other is the size of the Map and then iterate over the Map's keys and fill the array with each of the keys and it's associated value as you go.
some things to consider:
1) you're only after name and number, so just use the JTable's model.
2) JTable also has a built in rowSorter (java 1.6+)
3) a JFormattedTextField might be better than your JTextField/regex checking/error generation
4) use a better layout manager for TelephoneDirectory() - check what happens when the frame is dragged wider/leaner
5) clean up windowClosing - get rid of minimize, and the only code there should be to exit on 'YES', meaning the frame
should be set to DO_NOTHING_ON_CLOSE initially