How can I get the memory that my Java program uses via Java's Runtime api?

You're doing it correctly. The way to get memory usage is exactly as you described:

Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()

But the reason your program always returns the same memory usage is because you are not creating enough objects to overcome the precision limitations of the freeMemory method. Although it has byte resolution, there is no guarantee for how precise freeMemory needs to be. The javadoc says as much:

an approximation to the total amount of memory currently available for future allocated objects, measured in bytes.

Try the following, which creates two million NewObject instances, and prints out each time the result of freeMemory changes:

public static void main(String[] args) {
    Runtime rt = Runtime.getRuntime();
    long prevTotal = 0;
    long prevFree = rt.freeMemory();

    for (int i = 0; i < 2_000_000; i++) {
        long total = rt.totalMemory();
        long free = rt.freeMemory();
        if (total != prevTotal || free != prevFree) {
            System.out.println(
                String.format("#%s, Total: %s, Free: %s, Diff: %s",
                    i, 
                    total,
                    free,
                    prevFree - free));
            prevTotal = total;
            prevFree = free;
        }
        map.put(i, new NewObject());
    }
}

On my machine, I see output like the following

#0, Total: 513998848, Free: 508635256, Diff: 0
#21437, Total: 513998848, Free: 505953496, Diff: 2681760
#48905, Total: 513998848, Free: 503271728, Diff: 2681768
#73394, Total: 513998848, Free: 500589960, Diff: 2681768
#103841, Total: 513998848, Free: 497908192, Diff: 2681768
...

Notice how the reported free memory did not change until the 21,437th object was instantiated? The numbers suggest freeMemory for the JVM I'm using (Java7 Win 64-bit) has a precision of just over 2.5MB (although if you run the experiment, you'll see this number varies).

-- Edit --

This code is the same as above, but prints more details about memory usage. Hopefully it's a bit clearer how the JVM's memory usage behaves. We continuously allocate new objects in a loop. During each iteration, if the totalMemory or freeMemory is the same as the last iteration, we don't print anything. But if either has changed, we report current memory usage. The values represent the difference between current usage and the previous memory report.

public static void main(String[] args) {
    Runtime rt = Runtime.getRuntime();
    long prevTotal = 0;
    long prevFree = rt.freeMemory();

    for (int i = 0; i < 2_000_000; i++) {
        long total = rt.totalMemory();
        long free = rt.freeMemory();
        if (total != prevTotal || free != prevFree) {
            long used = total - free;
            long prevUsed = (prevTotal - prevFree);
            System.out.println(
                "#" + i +
                ", Total: " + total +
                ", Used: " + used +
                ", ∆Used: " + (used - prevUsed) +
                ", Free: " + free +
                ", ∆Free: " + (free - prevFree));
            prevTotal = total;
            prevFree = free;
        }
        map.put(i, new NewObject());
    }
}

On my notebook, I see the following output. Note your results will differ depending on OS, hardware, JVM implementation, etc.:

#0, Total: 83427328, Used: 1741048, ∆Used: 83427328, Free: 81686280, ∆Free: 0
#3228, Total: 83427328, Used: 1741080, ∆Used: 32, Free: 81686248, ∆Free: -32
#3229, Total: 83427328, Used: 2176280, ∆Used: 435200, Free: 81251048, ∆Free: -435200
#7777, Total: 83427328, Used: 2176312, ∆Used: 32, Free: 81251016, ∆Free: -32
#7778, Total: 83427328, Used: 2611536, ∆Used: 435224, Free: 80815792, ∆Free: -435224
...
#415056, Total: 83427328, Used: 41517072, ∆Used: 407920, Free: 41910256, ∆Free: -407920
#419680, Total: 145358848, Used: 39477560, ∆Used: -2039512, Free: 105881288, ∆Free: 63971032
#419681, Total: 145358848, Used: 40283832, ∆Used: 806272, Free: 105075016, ∆Free: -806272
...

There are a few observations from this data:

  1. Used memory tends to increase, as expected. Used memory includes live objects and garbage.
  2. But used memory decreases during a GC, because garbage has been discarded. For example, this occurred at #419680.
  3. The amount of free memory reduces in chunks, not byte-by-byte. The chunks vary in size. Sometimes the chunks are really tiny, like 32 bytes, but usually they are larger, like 400K, or 800K. So it appears the chunk size will vary a fair bit. But compared to total heap size, the variation appears tiny. For example, at #419681 the chunk size is only 0.6% of the total heap size.
  4. Free memory tends to decrease, as expected, until a GC kicks in and cleans up garbage. When this occurs, free memory increases pretty dramatically, depending on the amount of discarded garbage.
  5. This test generates a lot of garbage. As the hashmap grows in size, it rehashes its contents, thus generating a lot of garbage.

I've got the following methods

public static long getMaxMemory() {
    return Runtime.getRuntime().maxMemory();
}

public static long getUsedMemory() {
    return getMaxMemory() - getFreeMemory();
}

public static long getTotalMemory() {
    return Runtime.getRuntime().totalMemory();
}

public static long getFreeMemory() {
    return Runtime.getRuntime().freeMemory();
}

which return the (used) Memory in bytes.

If you want to recalculate to MiB I've got:

private static final long MEGABYTE_FACTOR = 1024L * 1024L;
private static final DecimalFormat ROUNDED_DOUBLE_DECIMALFORMAT;
private static final String MIB = "MiB";

static {
    DecimalFormatSymbols otherSymbols = new DecimalFormatSymbols(Locale.ENGLISH);
    otherSymbols.setDecimalSeparator('.');
    otherSymbols.setGroupingSeparator(',');
    ROUNDED_DOUBLE_DECIMALFORMAT = new DecimalFormat("####0.00", otherSymbols);
    ROUNDED_DOUBLE_DECIMALFORMAT.setGroupingUsed(false);
}


    public static String getTotalMemoryInMiB() {
        double totalMiB = bytesToMiB(getTotalMemory());
        return String.format("%s %s", ROUNDED_DOUBLE_DECIMALFORMAT.format(totalMiB), MIB);
    }

    public static String getFreeMemoryInMiB() {
        double freeMiB = bytesToMiB(getFreeMemory());
        return String.format("%s %s", ROUNDED_DOUBLE_DECIMALFORMAT.format(freeMiB), MIB);
    }

    public static String getUsedMemoryInMiB() {
        double usedMiB = bytesToMiB(getUsedMemory());
        return String.format("%s %s", ROUNDED_DOUBLE_DECIMALFORMAT.format(usedMiB), MIB);
    }

    public static String getMaxMemoryInMiB() {
        double maxMiB = bytesToMiB(getMaxMemory());
        return String.format("%s %s", ROUNDED_DOUBLE_DECIMALFORMAT.format(maxMiB), MIB);
    }

    public static double getPercentageUsed() {
        return ((double) getUsedMemory() / getMaxMemory()) * 100;
    }

    public static String getPercentageUsedFormatted() {
        double usedPercentage = getPercentageUsed();
        return ROUNDED_DOUBLE_DECIMALFORMAT.format(usedPercentage) + "%";
    }